OLD ANSWER - OUT OF DATE
I have followed all the same steps, and also see this bug. I suggest sending feedback inside the Authenticator app. (Tap the menu icon ⋮ in the top right, and then "Send Feedback").
Possible workarounds are:
1. Turn on "Two-step verification" in the Microsoft security page (same link as above: https://account.live.com/proofs/manage/additional ). When I enable two-step verification,, Authenticator sends codes correctly. Be aware: this setting will affect how you sign in everywhere. It also makes it harder to reset your password, or recover your account
2. Or, when you go to sign to Authenticator, look for "Scan a QR code". You may need to tap "Add an account" and "Personal account" first. This approach requires having a second device, that you can use to show the QR code to your phone camera :-). It's not really possible if you're only using a phone.
The QR code is provided by the Microsoft security page (same link as above: https://account.live.com/proofs/manage/additional). It is shown the first time you do "Add a new way to sign in or verify" > "Use an app".
If you have added "an app" before, these steps might not provide a QR code anymore. It might offer a QR code if you remove the "Send sign-in notification" option again. CAUTION: removing "Send sign-in notification" will also remove "Enter a code from a verification app". E.g. if you use Google Authenticator as a backup, this will stop working.