Parece que tudo o que você quer fazer é extrair o arquivo .deb , adicionar o arquivo .desktop e reconstruir o pacote. Este é um processo bastante simples. Para extrair:
dpkg-deb -R package.deb extract_dir
Note que -R é um extrato bruto para obter os arquivos de controle também. Em seguida, crie /usr/share/applications/ , se ainda não existir:
mkdir -p extract_dir/usr/share/applications/
Em seguida, basta adicionar seu arquivo .desktop (tome cuidado para que o nome não entre em conflito com qualquer outra coisa que você possa instalar) e reconstrua:
cp desktop_file.desktop extract_dir/usr/share/applications/
dpkg-deb -b extract_dir package_new.deb
Note que você também pode usar dpkg-deb -b extract_dir . para criar o pacote com seu nome canônico, mas provavelmente terá que tirar seu original do caminho primeiro ou então ele será destruído.