Technically, the login is managed by a display manager. You probably mean login is managed by GDM (Gnome Display Manager), which is not the same as Gnome (the desktop environment).
In Debian, it's pretty simple to switch. If you want to get rid of GDM and switch to KDM, just do this:
apt-get remove gdm
(alternatively, to remove any configuration files as well, use "apt-get --purge remove gdm)
apt-get install kdm
If you don't think you need to get rid of GDM, just do "apt-get install kdm". Either way, you'll get a screen with a choice of which display manager to use; you can then just select KDM.
I suspect the second problem may take care of itself after you install KDM, but if it doesn't, you can look for more help by entering "help:/kdm" in Konqueror's location bar. In section 4 on "configuring KDM" there is a subsection named "Shutdown".