Even stranger thing is that when I want to restart the computer it has restarted always without any problem.
Today I finally find out a solution:
Edit the kdmrc file:
$ sudo nano /etc/kde4/kdm/kdmrc
Change one line in section [Shutdown]. It looked like this:
So I changed it to:
HaltCmd=/sbin/shutdown -P now
Now logout from KDE. Switch to console with Ctrl+Alt+F1 and restart the kdm:
$ sudo /etc/init.d/kdm stop
$ sudo /etc/init.d/kdm start
After login to KDE again, perform the shutdown. Now it works again!