By my knowledge
By my knowledge the KDE is using the kbuildsycoca4 to build the KDE menu cache. The launchers are then using the cache to search and launch the programs.
Searching...'update kde menu' -> https://bbs.archlinux.org/viewtopic.php?id=64514
If the KDE menu is not updating automatically you could try to run the kbuildsycoca4 from the Konsole.
:~$ kbuildsycoca4 --help
Usage: kbuildsycoca4 [Qt-options] [KDE-options] [options]
Rebuilds the system configuration cache.
Generic options:
--help Show help about options
--help-qt Show Qt specific options
--help-kde Show KDE specific options
--help-all Show all options
--author Show author information
-v, --version Show version information
--license Show license information
-- End of options
Options:
--nosignal Do not signal applications to update
--noincremental Disable incremental update, re-read everything
--checkstamps Check file timestamps
--nocheckfiles Disable checking files (dangerous)
--global Create global database
--menutest Perform menu generation test run only
--track <menu-id> Track menu id for debug purposes
Launchers
The KDE has plenty of launchers: http://www.kubuntuforums.net/showthread.php?59851-KDE-Application-Launchers .
The Mangonel advertise:
Mangonel, a simple application launcher for KDE4.
Mangonel is intended as a light weight replacement for the, in my
view bloated and slow, standard KRunner...
The Mangonel is available from the Ubuntu repositories: http://packages.ubuntu.com/search?keywords=mangonel&searchon=names&suite=all§ion=all