Procure o arquivo /usr/share/applications/virtualbox.desktop
. No meu sistema, tem o seguinte conteúdo:
[Desktop Entry]
Encoding=UTF-8
Version=1.0
Name=Oracle VM VirtualBox
GenericName=Virtual Machine
Type=Application
Exec=VirtualBox %U
...
Basta alterar a parte Exec
para apontar para o seu script / executável personalizado.
Veja também
resposta de Thomas Nyman para uma pergunta semelhante.