Vejo que você está seguindo as instruções do arquivo de desktop do gnome. Tente seguir a documentação de instalação do carteiro aqui
Quando tentei instalar o Postman, o ícone só apareceu no menu do meu aplicativo gnome depois que eu executei sudo ln -s /opt/Postman/Postman /usr/bin/postman
das instruções.
EDIT: A partir da versão 6.1.3, execute sudo ln -s /opt/Postman/app/Postman /usr/bin/postman
.