I managed (finally) to solve the issue in this way:
- I went to my Microsoft account security info page: https://mysignins.microsoft.com/security-info
- I added the sign-in method via authenticator app (Select "Add sign-in method" and select "Authenticator App")
- By following the wizard the wished QR code appeared. In my new phone I opened my account and scanned the QR code.
Ta-da! The account was set up!