Adrian,
It really matters whether you are using Microsoft Authenticator with a Work or School account (Azure AD) where an Administrator can remove the 2FA requirement from the account at least temporarily or instead using a personal Microsoft account, where if available you should be able to use a different 2FA authentication method like alternate email or text to receive a code in order to login and change the Advanced security options item titled Send sign-in notification, removing it in order to allow setting it up again properly.
The links to proper methods for setting up Authenticator for both type of accounts are provided in my previous long post, since though the Authenticator app used is now the same, the process for each of these are different due to the different back-ends for Azure AD and Microsoft 365/Outlook personal accounts.
Ben Coor also mentioned in his last post above that in his case, an apparent user of a Work or School account had Authenticator previously configured on another phone that must have been interfering with the new installation.
What exactly is happening in a specific case is not always the same, so you need to fully understand your particular environment and potential issues, since there's no way anyone can provide a single answer that applies to every possible situation.
Rob