Você pode instalar alacarte para editar as entradas do menu.
Em distribuições baseadas no Debian:
sudo apt-get install alacarte
Caso contrário, como você observou, as informações estão em .desktop arquivos nos locais fornecidos (em particular, a Exec line).
Eu apenas faço:
grep -iR "name that shows up in menu" ~/.local/share/applications /usr/share/applications
Em seguida, basta olhar as linhas Exec dos arquivos que parecem candidatos prováveis.