MFA catch-22 during onboarding due to registration policy

I would make the Microsoft Authenticator pushed by default to the devices assuming these are company devices. This will reduce the amount of steps users are required to do during onboarding and will also solve for the problem of needing to sign into the company portal. 

As Vasil suggested, I would start to move the business into the direction of assigning TAP codes for initial onboarding, this will also prevent these loops you are seeing with conditional access and MFA registration policies.