Adicione uma nova ação na Ferramenta de Configuração de Ações do Nautilus, chamada "Executar no Terminal".
O comando relevante é simples:
gnome-terminal -x %f
Então, adicione isso na aba Comando

Parasempremanteroterminalabertoaoexecutarestaação,useumperfildoGnomeTerminalcomessaconfiguração:Emgnome-terminal,EditarPreferências,selecioneaguia'Perfis',adicionenovoperfileligue"segure" e, na guia "Comando", marque para mantê-lo aberto:

adicione--profile=holdaosparâmetrosdoterminalgnome

(Sobrecomoadicionaressaconfiguraçãoemoutrosemuladoresdeterminal,consulte ESTA resposta.)
Em seguida, na guia Mimetypes , adicione application/* .

Certifique-sedequesobaaba'Ação'daFerramentadeConfiguraçãodeAçõesdoNautilus,vocêtenhaselecionadoaconfiguraçãoparaexibiraopçãonomenudecontextodaseleção.
Salvar.