Basta mover seu executável do diretório onde ele está para a área de trabalho usando o mouse. Ou se você quiser mantê-lo em seu diretório original, crie um symlink.
Dependendo se eu uso um shell script com a extensão .sh ou um programa c compilado (apenas com o nome a.out) os ícones parecem diferentes, os links simbólicos mostrando algumas setas adicionais, mas os programas estão sendo executados ok.
Do que você escreve, o programa é obviamente executável por você.
O que acontece quando você clica com o botão direito no arquivo? Você vê uma opção para executar o programa?