I am using Arch Linux with KDE 4.4.5.

The problem is that in the "Leave" tab of the K Menu, there are no "Shutdown" and "Restart" options. I've seen that they do exist in other distros, so why not here?

I'm tired of having to "Logout" (which takes a very long time for some reason) and then typing "sudo shutdown -h now" every time.

If your menu is not extended far enough, those options may be hidden.

Are you using a login manager at all? Some of these options might not be present if there's no display manager active, such as kdm or gdm. You seem to be login in from command line, is that true?

Modern gnome versions that use consolekit to manage this stuff can be run this way, which will give you the ability to manage sessions even if there's no display manager.

This also grants privileges to processes needing them such as nautilus (to mount drives and that stuff). But I have no idea if kde 4.x has this capability. If not, just use kdm to login.

Yeah, that's right. From Slack's /etc/inittab:
Using runlevel 3 and startx = no restart and shutdown options in KDE menu.
Booting into runlevel 4 = options available.

Yes, I log into the GUI using startx.

Do you think it would be worthwhile to install a display manager (probably KDM)?

I installed KDM and everything's fine now.

Only you can answer that.

If kde has other means to do session handling then you could use something similar to that solution I posted above for gnome.

If not, then you will have to decide yourself between a lighter login and that features.