Can you also post the output when you select "kdm" instead of "kdm-kde4"
As a workaround you should be able to do "echo /usr/bin/kdm | sudo tee /etc/X11/default-display-manager" to set kdm as the default, then "sudo /etc/init.d/kdm start" should work.
Can you also post the output when you select "kdm" instead of "kdm-kde4" default- display- manager" to set kdm as the default, then "sudo /etc/init.d/kdm start" should work.
As a workaround you should be able to do "echo /usr/bin/kdm | sudo tee /etc/X11/