A user in my organization was having the same problem and looking for an answer I found this thread.
I was able to figure it out so I figured I'd come back here and let you guys know how I fixed it, in case it's helpful to someone else.
The problem was that the user had installed the Authenticator app in a previous phone which she lost in a lake, so when she was trying to install the Authenticator app on the new phone, the system was trying to authenticate the account sending a code to the old phone, creating a loop.
To fix it, I logged in to MS Admin Center and went to the Identity (Microsoft Entra) Admin Center.
In Entra, went to Users and clicked on the user with the issue.
In the user's profile, click on Authentication methods under the Manage section, and under Usable authentication methods delete the Authentication method "Microsoft Authenticator" which said iPhone 11 in the Detail column (the user's old phone was an iPhone 11, that's how I knew!)
After deleting the old authentication method, the user was able to setup the authenticator app on the new phone.
I hope this helps someone.