xdg-desktop-icon adiciona um ícone à área de trabalho do usuário atual, não adiciona entradas aos menus de todos os usuários.
desktop-file-install instala .desktop arquivos no diretório de aplicativos do usuário quando executado como um usuário que não seja root e para /usr/share/applications se executado como root (obrigado por apontar isso), para que você possa usar que para instalar uma entrada de aplicativo no menu.
Você também pode instalar um aplicativo no menu para todos os usuários manualmente; tudo o que é necessário para criar um arquivo .desktop e copiá-lo para /usr/share/applications .
Para aplicativos não empacotados, você também pode usar /usr/local/share/applications (criando-o, se necessário); que funciona pelo menos no Debian 8. Então, com desktop-file-install você executaria (como root )
desktop-file-install --dir=/usr/local/share/applications ...
Veja "Arquivos de área de trabalho" e a especificação relevante para mais detalhes.