That sequence is a reasonable starting point. The UPN and primary email address are separate changes, so check both after the sync rather than assuming one changed the other.
For each user, set the new UPN in AD. In proxyAddresses, use uppercase SMTP: for the new primary address and lowercase smtp: for the old address you want to retain. Make sure there's only one uppercase SMTP: entry, and preserve any other aliases that are still needed.
Sync and verify a small group first. Check the UPN and addresses in Microsoft 365, then test mail delivery to both domains before changing sign-in instructions for everyone.
7q~fusecase_314:
Keeping the old address as a mail alias doesn't by itself establish that it will work as a sign-in name. Check the sign-in configuration separately.