Hi @GS
Thank you for posting this in Microsoft Q&A.I understand you're having trouble setting up a working authentication policy in your Azure AD tenant. You've tried using per user MFA settings and it works fine, but when you try to use Conditional Access with password less MFA, the user is prompted to set up the Microsoft Authenticator app but is unable to complete the setup process.
Can you check phone sign-in enable on your Microsoft authenticator. If not, please enable phone sign-in on your Microsoft authenticator. After users registered themselves for the Microsoft Authenticator app, they need to enable phone sign-in.
Please follow the steps which mentioned in this document: Enable phone sign-in
Have you tried with Require multi factor authentication under grant controls instead of going password less MFA in conditional access policy. If you are used what is the behavior of that policy.
Hope this helps. Do let us know if you any further queries.