I have exactly the same issue which occured after installing the Authenticator on a fresh Android profile.
After removing the working office365 work account on my existing Android profile and re-adding the account into Authenticator I ran into the very same issue again.
Now I have two Android profiles without functioning push notifications.
Authenticatior version: 6.2208
Android 12 on OnePlus Nord with multi-profile enabled
Prefered 2FA method: Push notification