所有しているのは4K版ではなく無印ですが、トラブル対処法は同じだと思います。

　自宅で使用しているBuffaloのWi-Fiルーターが調子悪くなったので交換したのですが、他のWi-Fi機器には問題なく接続できるのにAmazon Fire TV Stickだけ接続できないというトラブルに見舞われました。Amazon公式サイトに記載されている、Fire TV StickをWi-Fiに接続できない場合のトラブルシューティングを簡単に説明すると以下の通りです。

（１）Fire TV Stickの電源を切る→入れる

（２）Wi-Fiの設定を確認し、画面の指示に従う

（３）Wi-Fi接続をいったん切る→入れる

（４）使用しているモデムやルータを再起動

（５）端末を工場出荷時に初期化

（引用：Amazon ヘルプ＆カスタマーサービス）

　結論から言うと、（４）を試したところ接続が復活しました。自宅のネット回線はモジュラージャック→モデム→ルーター→Wi-Fiルーター（Buffalo）……各Wi-Fi機器の順番で繋がっているのですが、モデムとルーターとWi-Fiルーターの電源をいったん全部落とし、モデム、ルーター、Wi-Fiルーターの順番で電源を入れていきます。その際各機器はネット回線の接続が確立してから（ステータスランプが正常に点灯してから）次の機器の電源を入れます。すると何度やっても正しいバスワードを弾いていたFire TVがあっさりWi-Fiを認識し、接続してくれました。

　トラブルを避けるため、入れ替えたBuffaloのWi-Fiルーターは旧Wi-Fiルーターの設定（ネットワーク名やパスワード）をそのまま引き継いだのですが、iPadもiPhoneもWin PCもMacのどれも何もしなくてもあっさり繋がるのに、どうしてFire TVだけこんなに苦労させられるのでしょう？搭載しているAmazon製のOSのデキが悪いとしか言いようがないですね。以前Amazon Fireタブレットを所有していたのですが、そのOSもなんだかちょっと扱いづらかった記憶があります。本体が安い分をスペックダウンやOSの手抜きで補っているのでしょうか？　やれやれです。