Well the easiest way to edit the K-Menu is with kmenuedit but if you need/want to do it from the command line the following link may be of some use
http://www.linuxquestions.org/linux/...for_SUSE_Linux
It's written for Suse but it should be fairly similar for what you're using, which I assume is Ubuntu. I'm not an Ubuntu user so it may be the same as Suse but it's also possible the files will be in a slightly different location, for example on my Gentoo install they're in /usr/kde/3.5/share/applications/kde/ rather than /opt/kde3/share/applications/kde.
As for setting up APT to do what you want I'm not sure, does it not automatically add installed programs to the K-Menu which you could then just move manually to the directory you want?