日本語で検索するとRootJunkyばっかりのクソ情報が多いけど、
あれはPlayStoreの中身超古いし不安定だしUSBデバッグとか必要ない作業ばっかり

ここのFor Amazon Fire HD 8 2016 [6th Gen] Fire OS 5.3.3.0, のapk x 4 を
順番にインストールする方が安定(HD8じゃないFire2015もOK)

http://blog.notfaqs.com/2017/05/android-install-google-play-store-on.html

Playストアのバージョンはちゃんと7.8.16-P-all[0][PR]になってる？
ならOK

最近かってにアイコンアップデートされたけどこれも自動で勝手に適用されたよ