Das war bisher kein besonders großes Problem, einfach die passenden apks holen und installieren. Mit der 8^th Generation, geht das aber genau so NICHT. Also habe ich Tage zugebracht, bis ich den Artikel gefunden habe:
https://forum.xda-developers.com/amazon-fire/help/fire-os-6-3-x-play-store-fire-hd-8-t3850363/page6

Die Kurzfassung

Wenn es nicht geht

Ein factory reset und die externe Speicherkarte unbedingt als portable installieren. Welche Versionen man nimmt ist ziemlich egal, man kann ruhig die neuesten für Android 7+, nodpi, 64bit arm nehmen.

Quellen

apkmirror bietet da genug Auswahl:

• Services Framework
• Account Manager
• Play Service
• Play Store