First things first - are those users provisioned directly in the cloud or being synchronized from AD/external system? In the latter scenario, you will need to make the changes there and wait for sync to happen.
If they are managed directly in Azure AD, you can use the following cmdlet:
Set-Mailbox user@domain.com -WindowsEmailAddress new@domain.com
The above will add new@keyman .com as the current primary SMTP address, while keeping the old one as secondary address, and is the easier way to make this change in O365. You can run this in bulk based off a CSV file or just directly leverage the firstname/lastname values for each user. Here's an example for the former:
https://social.technet.microsoft.com/Forums/msonline/en-US/66165391-1bb9-4925-a2e7-fbe701654b00/bulk-change-primary-smtp?forum=onlineservicesexchange