Unfortunately, you cannot automate this as Exchange Online does not support email address policies. Thus your best option is to use PowerShell. The solution will vary depending on whether you want to add the address as primary or secondary alias, but in both cases is fairly easy to do:
Get-Mailbox -RecipientTypeDetails UserMailbox -ResultSize Unlimited | % {Set-Mailbox -WindowsEmailAddress $_.PrimarySmtpAddress.Replace("tenant.onmicrosoft.com","newdomain.com") }
or
Get-Mailbox -RecipientTypeDetails UserMailbox -ResultSize Unlimited | % {Set-Mailbox -EmailAddresses @{add=$_.PrimarySmtpAddress.Replace("tenant.onmicrosoft.com","newdomain.com")} }
Make sure to replace the corresponding domain names, and of course, test against a user or two before running it across the company. Even better, expand these examples into a full-blown script with proper error checking and such. Here's one such example from Tony: https://office365itpros.com/2022/10/18/update-user-email-upns/