Le "autoremove" sert à enlever tous les paquets qui traînent sans pour autant être nécessaires, ça inclut les vieux noyaux mais aussi les dépendances des logiciels que tu désinstalles.
Ceci dit comme tu l'as trouvé :
we can't remove the package
Donc pas la peine d'essayer de désinstaller quoi que ce soit, la commande
sudo rm /usr/share/applications/ubuntu-amazon-default.desktop
devrait suffire à cacher l'icône