We had a similar behaviour when we were pushing MS Authenticator and CP in separated app policies.

 I assume you have the managed app config for Authenticator in the app policy. (enabled shared device mode, pre-fill tenant id and token registration). We had a strange issue with managed apps, some applications were not installed with managed app configs (including MS Authenticator).The only fix was to recreated the device groups again (with all profiles and polciies)

Since having all MS apps in the same policy still not working ok for you (i didn't had any more issues with this setup: Authenticator - high-priority and open after insall, cportal - postponed priority, and don't open any ms apps before the device is registered), you can try to exclude cp portal from that policy, and create a separate one, and apply it with a filter (ex: if authenticator is installed)