Macの復元方法はありますか

端末を消去しただけでは、探すはオフになりませんよ。

探すをオフにするには、端末を解除にする必要があります。

探すをオフにする必要があるのはiPhoneだけだったのですか？

設定の探すでオフにすればそれだけでよかったのですが。ただ、その前に盗難デバイスの保護もオフにしておく必要はあります。

ご質問の件ですが、macも消去してしまったのなら、バックアップがない限り、復元することはできません。ただ、もう一度再設定して、同じApple Accountにすれば、icloudで同期してる分（メモ、連絡先など。設定でicloud写真がオンだったのなら、写真、Apple MusicをサブスクライブしてればApple Music）に関しては元に戻ります。icloudで同期してたとしても、写真は戻るのに時間はかかるかも（何日単位）。