You can do this all with set-mailbox and the Exchange Powershell:
Create a csv with two columns and populate the values for :
UserPrincipalName
(Current UPN)
PrimarySMTPAddress
(New UPN and Primary SMTP)
then with Exchange online powershell:
$mailboxes = import-csv Mailboxes.csv
$mailboxes |% {Get-mailbox -UserPrincipalName $._UserPrincipalName| Set-mailbox -UserPrincipalName $._PrimarySMTPAddress -PrimarySMTPAddress $._PrimarySMTPAddress}
Test with just a few first!!!!!
Then if it looks good, run against the entire list