Если в пакете есть .desktop файл, в меню программа должна прописаться.
$ dpkg -L audex | grep desktop
/usr/share/applications/kde4/audex.desktop
/usr/share/kde4/apps/solid/actions/audex-rip-audiocd.desktop
Полдня ставлю разные программы - что должно было появиться в меню, появляется.
Попробуй kbuildsycoca5 --menutest, посмотри, что там есть.
Перестроить всё глобально - kbuildsycoca5 --global. В системе ещё может быть kbuildsycoca4 - может быть, обоими программами.