「yyyy0101」を「19000101」に置換すると、エクセル上で「＊」になる。

「*」ではなくて、「#######」のような感じになる、ということだと思いますが、そのセルに設定されている書式が「数値」になっていないでしょうか（もしくは、ユーザ定義で数値系の指定）。

セルの値が数値と判定できる場合、書式が「数値」になっていると負号の分の一文字が頭につきます（正の値なら空白）。
そして、セルの幅を超える桁の値の場合に、セルの表示は # で埋められたものになります。

もし、上記の条件に合致するなら、

• セルの書式を「標準」にする
• セルの幅を少し広げて、9～10 文字程度表示できるようにする

のどちらか（もしくは両方）をすると、見えるようになります。

置換対象のセルの場所がばらばらで、いちいち書式を設定するのが面倒だ、ということであればマクロを使うことになります。