Basicamente, esses itens de menu são arquivos .desktop. Os caminhos habituais são:
~/.local/share/applications
/usr/local/share/applications
/usr/share/applications
Para continuar com o seu exemplo:
[workstation] user ~ >cat /usr/share/applications/vncviewer.desktop
[Desktop Entry]
Name=TigerVNC Viewer
Comment=Connect to VNC server and display remote desktop
Exec=/usr/bin/vncviewer
Icon=tigervnc
Terminal=false
Type=Application
StartupWMClass=TigerVNC Viewer: Connection Details
Categories=Network;RemoteAccess;
Eu sugiro que você primeiro verifique se esses arquivos .desktop foram bem criados.
Se não estiver armazenado no mesmo caminho, você poderá procurar por aqueles com o seguinte comando: find / -name '*.desktop'
Se você não encontrar esses arquivos, poderá criá-los usando o modelo do meu vncviewer.desktop