I got same error with my test Azure tenant and after changed some Azure AD setting, it finally worked.
configurations need to be done on Azure AD ( by global admin ):
- in AAD -> Enterprise Application, search "Azure Mul" ( application type is "Microsoft applications" ), then enable "Enabled for users to sign-in" option for Azure Multi-Factor Auth Connector ( There is another application "Azure Multi-Factor Auth Client", might need to do the same ).
- Add your user or a proper group into the application's "Users and Groups" so you are allowed to use the app.
- Make sure in AAD -> Security -> "Authentication methods", "Microsoft Authenticator" is enabled for all users.
on client side, the device need to be registered into Azure AD.