Crie um arquivo .desktop com isto:
[Desktop Entry]
Version=1.0
Name=Python Script Name
Comment=Open Python script (name)
Exec=python "/home/user/path with any spaces/to/script.py"
Icon=/usr/share/pixmaps/idle.xpm
Terminal=true
Type=Application
Categories=Application;
Salve em /home/user/.local/share/applications
Torne-o executável clicando com o botão direito do mouse, indo para a guia permissões e marcando "Permitir execução como programa"