Un logiciel n'apparait pas forcément dans ton menu kde. Mais il est très probable que tu puisse y accéder en ligne de commande si l'installation s'est bien déroulée. Supposons que tu recherche firefox et thunderbird. Ouvre une console root (superutilisateur) et tape :
updatedb
locate firefox
locate thunderbird
updatedb met à jour une base de donnée indexant les fichier de ton pc. Il faut donc lancer cette commande de temps en temps pour que ton locate soit cohérent avec la réalité.

Si tu connais le nom exact du binaire (l'exécutable) tu as plus rapide. Par exemple, pour ghostview :
whereis gv
gv: /usr/X11R6/bin/gv /usr/bin/X11/gv
Une fois l'application trouvée, il suffit de la rajouter dans ton menu démarrer, par exemple à l'aide de kmenuedit (ouvre une console utilisateur et tape kmenuedit). Sous mandriva tu dois aussi pouvoir y accéder par le centre de controle kde.

Bonne chance