Boa noite arcashaid!
O procedimentos de remoção é esse mesmo que você realizou, remover a pasta do programa. Ele não realiza nenhuma instalação no sistema. quando você executa o script "Magarena.sh", ele apenas chama o programa à execução.
Com relação ao ícone, provavelmente se refere ao atalho (link) que ele criou, ou você mesmo à criou. É só removê-lo que ele sairá de lá. Caso não esteja conseguindo, provavelmente é problema de permissão. Para remover, basta executar o comando abaixo no diretório onde se encontra o ícone.
$ sudo rm -rf nome_do_icone
Caso não tenha conseguido, favor informar o passo a passo que você realizou para que possamos lhe ajudar.
Abraço!