A Microsoft app for iOS and Android devices that enables authentication with two-factor verification, phone sign-in, and code generation
I had the exact same problem. When I launched the Microsoft Authenticator app the first time, I didn’t click restore from backup, I just logged in. I deleted the app and reinstalled and still no option to restore from the backup.
This is what I was able to do:
on new iphone
go to settings-your name-iCloud-see all- then UNCHECK Microsoft Authenticator. Reinstall the Authenticator app. When you do that, it brings back the option to restore from backup when you launch the app!