GreigMitchell You can enable the synchronization of the UserPrincipalName attribute.
To check whether this feature is enabled run
Connect-MSOLService
Get-MsolDirSyncFeatures
and check if SynchronizeUpnForManagedUsers is enabled.
Caution: Setting SynchronizeUpnForManagedUsers to $true is a one-time operation and cannot be undone.
If it is true (which probably is not the case in your environment) then the UPN should be updated in the cloud after you change it on-premises. This can take a while.
An automation to match the email address to the UPN does not exist. Best you can do is having an active EAP that updates the email address based on the alias (mailNickname in Active Directory). In that case, when you change the UPN, you must change the alias, too.
The easiest way to do all of this in one step is to use Set-RemoteMailbox:
Set-RemoteMailbox jon.doe@example.com -UserPrincipalName jon.dane@example.com -Alias jon.dane
And if you're like and like a clean user object, you can change the RemoteRoutingAddress with it as well:
Set-RemoteMailbox jon.doe@example.com -UserPrincipalName jon.dane@example.com -Alias jon.dane -RemoteRoutingAddress jon.dane@example.mail.onmicrosoft.com
If you do not have an EAP, add the -PrimarySmtpAddress parameter.
The UPN change at Microsoft will take a while.
If SynchronizeUpnForManagedUsers is false, then you need to change the userprincipalname manually by using the Set-MsolUserPrincipalName cmdlet.