macOSがCatalinaになってないのでは?
復旧ユーティリティの画面でmacOSの再インストールにすると、macOSのアイコンが出てきますが、Catalina島の絵になってますか?
option + command + Rとしてインターネット復元に持ち込んでますか?optionキーの押し方が不十分ということはありませんか?それともshiftキーも一緒に押してしまってるとか。フォーマットでAPFSが出てこないなら、APFSをサポートしてないmacOSバージョンの復旧ユーティリティになってるのではないかと思います。
macbook pro 2012だと、工場出荷時のmacOSバージョンは10.7.xですので、そのバージョンの可能性があると思います。
そのmacを受け取った時のmacOSバージョンは何だったのでしょう?
もし、そのmacが過去にhigh sierra以上のバージョンにしたことがないとかだと、ファームウェアの関係で、option + command + RとしてもCatalinaの復旧ユーティリティにはならないかもしれません。もしそうなら、単に、command + Rとする方が良いかも。
取り敢えずは、とにかくmacOSをインストールすれば良いのですが、後のことを考えると、少なくとも、10.11以上のmacOSをインストールする方が良いです。command + Rでインターネット復元にすれば、少なくとも、直前のmacOSバージョンの復旧ユーティリティで立ち上げられると思います。Catalinaより古いバージョンのmacOSしかインストールできない場合は、取り敢えずそのバージョンにしてCatalinaにアップデートすることになります。
でも、Mojave(10.14)以前のmacOSバージョンだと、現在では、サーバエラーになってインターネット復元でインストールできないと思います。
option + command + Rでインターネット復元でCatalinaの復旧ユーティリティに持ち込めるのが最善です。