これは、文字コードの問題というより、文字コードの自動判別に失敗しているメモ帳の問題だと思います。
既存のテキストファイルの文字コードを変換するのではなく（無数にあるでしょうし）、
通常使用するテキストエディタを、メモ帳から他のものに変更したほうがいいと思います。
メモ帳は、Windowsに最初から入っているテキストエディタというだけで、
機能的にはずっと他のテキストエディタに劣後してきましたから。

メモ帳のデフォルトの文字コードがShift_JIS（ANSI）からUTF-8になったので、
他の環境との互換性が高まった分、Windowsの新旧間で問題が発生しやすくなるのは、ある意味仕方がありません。
本件は、メモ帳の文字コードの自動判別がうまく機能していないように見えるので、
どうしてもメモ帳を使い続けたいのであれば、Microsoftにメモ帳の機能改善を要求するしかありません。

それよりも、もっと高性能なテキストエディタをインストールし、テキストファイルに関連付けして使ったほうが、
いろいろと融通がきくし、便利になるのではないかと思います。
たとえば、フリーソフトなら「TeraPad」、シェアウェアでもよければ「秀丸エディタ」とか。
もちろん、テキストエディタは他にも多数あるので、好みのものでいいんですが、
両方とも個人的に使ったことがあり、軽量かつ安定しているので、
シンプルなテキストエディタとしての用途に合っていると思います。

おすすめはしませんが、どうしても既存のテキストファイルの文字コードを変換したいのであれば、
「FileCode Checker」等を使って、文字コードをUTF-8に変換すればいいと思います。

ただし、テキストファイルの文字コードは、基本的にテキストファイルの作成者が決めるものです。
むやみに文字コードを変換すると、他のソフトウェアの誤動作の原因になる可能性があります。
既存のデータに変更を加えるのではなく、テキストファイルを開く方法を変えるべきだと思います。
決して、Shift_JISがダメというわけではありませんので。
たとえば、古い環境との互換性やデータサイズの面では、Shift_JISのほうが有利です。