新UIのGoogle Playストアについては、UIが大幅に刷新されたGoogle Playストア v4.0.25がリリース&手動でアップデートする方法。を参照してください。
今回は、Kindle Fire HDに既にインストールされているGoogle Playストアをアップデートする形でインストールしました。
Kindle Fire HDにGoogle Playストアをインストールする方法は、Kindle Fire HDでGoogle Playストアを使う方法。を参照してください。
また、上記リンク先のGplay3.8.17.apkの代わりに今回のapkファイルをインストールしても問題なく動作しています。
今回のインストールには、ESファイルエクスプローラーを使っています。
http://forum.xda-developers.com/showthread.php?t=2242398から「com.android.vending-1.apk」をダウンロードして、Kindle Fire HDの内部ストレージにコピーしておきます。

ESファイルエクスプローラーでcom.android.vending-1.apkをタップすると、インストールするか尋ねてくるので「OK」をタップします。

「com.android.vending-1.apk Install Succesfully」と表示されれば、新しいUIのGoogle Playストアへのアップデートは完了です。

Google Playストアを起動してみると、新しいUIで問題なく動作しています。

なお、現在Google Playストアは、v4.0.27が配信中です。
v4.0.27はDownload: Latest Google Play Store 4.0.27からダウンロードできるので、こちらをインストールしてみてもいいですね。
Kindle Fire HDで新しいGoogle Playストアを使いたい人は試してみてください。