To regain access to your authenticator codes after changing your phone, you should first check if you had set up a recovery account in the Microsoft Authenticator app on your old device. If you had enabled iCloud backup in the Microsoft Authenticator settings, you could restore your codes by signing into your personal Microsoft account on the new device and tapping "Begin recovery."
However, since you mentioned that your new phone's Microsoft Authenticator app is blank and that it says there is no backup stored in your iCloud account, it seems you may not have completed the backup process before erasing your old phone. Unfortunately, without a backup, you may need to reset the two-step verification settings for the accounts that were using the Authenticator app. This typically involves contacting the support for those services to regain access.
If you had SMS or call-based multi-factor authentication (MFA) set up, you might still be able to use those methods to verify your identity and regain access to your accounts.
References: