I had exactly the same issue (Selecting 'approve' on the app popup - always returned 'denied'.)
The problem was witnessed in android Microsoft Authenticator (v 6.2212.8187)
The solution (for me) was to DISABLE the "App Lock" feature of Microsoft Authenticator. This feature basically asks the device unlock password every-time you "open the app, approve a notification or autofill on sites and apps".
So it would seem, for whatever reason, the app is unable to show both the approval popup and the device unlock password "window" (at the same time). The device unlock password is never shown, hence the approval is denied.
I'll continue to investigate for a "better" solution, but for now, I can verify that disabling "App Lock" feature works for me.
The feature can be disabled/enabled in Microsoft Authenticator -> three dots (top right corner) -> Settings -> Security -> "App Lock" (On/Off)