Microsoft アカウントにサインインを求められ、サインインが完了できないのはスマートフォンだけですか? PC から同じアカウントで Microsoft account | ホーム や 追加のセキュリティ オプション (live.com)にサインインできますか?
追加のセキュリティ オプション (live.com) にサインインできれば、AUthenticator を再登録することができますし、他の本人確認手段を追加することもできます。
追加のセキュリティ オプション (live.com) へのサインインで Authenticator での認証を求められて、サインインできない場合は、Microsoft アカウントのセキュリティ情報と確認コード の「セキュリティ情報の管理」- 「セキュリティ情報を更新する」に書かれているように [すべての情報が不明] を選択し、画面に表示される指示に従ってセキュリティ情報を置き換えます。詳しくは以下を参照してください。