I'm glad that you were able to resolve your issue and thank you for posting your solution so that others experiencing the same thing can easily reference this! Since the Microsoft Q&A community has a policy that "[The question author cannot accept their own answer. They can only accept answers by others] (https://docs.microsoft.com/en-us/answers/support/accepted-answers#why-only-one-accepted-answer)**)", I'll repost your solution in case you'd like to "[Accept] (https://docs.microsoft.com/en-us/answers/support/accepted-answers#accepted-answer-in-a-question-thread)**)" the answer.
Issue: Getting error while registering multi-factor authentication for a business user in Microsoft 365.
Solution: Issue was resolved by choosing to use a different authenticator app instead of Authenticator app which was used earlier.
Please "Accept the answer" if the information helped you. This will help us and others in the community as well.