Same problem here.

Salesforce authenticator on my phone can show my heroku account, with a 6-digit code, Heroku, and my name. However, everytime I try to log in, no notification pops up on my phone. Every time I insert the code, it fails.

I completed the setup of adding Salesforce Authenticator by Manage Account -> Manage Multi-Factor Authentication -> One-Time Password Generator -> scanning QR code with my phone.

It seems that my phone know the existance of my Heroku account. It just doesn't help me to log in.