Perdonami, io ho comprato 31 Fire TV Stick e 1 Fire Cube, su tutte ho installato Kodi e su tutte appare l'icona quindi il problema non è di Kodi o Fire OS in questo caso ma di quella Fire TV Stick in particolare, vai a capire perchè, l'unica cosa che mi sento di consigliarti è di provare a fare un reset perchè Kodi ha la sua icona, magari con l'occasione aggiorni anche la versione di Kodi (l'ultima stabile è, al momento, la 19.3 ma comunque l'icona l'aveva anche la 18.x); di Fire 4k in particolare ne ho acquistate solo 2 (di Max invece solo 1) ma, come detto nessuna ha dato problemi anche adesso dopo gli aggiornamenti.
Edit: Errore mio la procedura più semplice per creare apk con logo che linkano quelle senza logo (che comunque devo essere installate) si trova qui:
http://atvlauncher.trekgonewild.de/index.php
Fammi sapere se riesci questa è veramente molto semplice, io comunque nel caso la volessi provare ho già preparato quella di Kodi, mi viene però il dubbio che se la tua Fire non visualizza le icone di tutte le app "esterne" non visualizzi neanche questa, ma vale la pena comunque provare.
Buona Domenica.