The best way I have found to handle this is to export all the related contacts with an email or companies with a domain and re-format in Excel. After altering, I then bulk import the files back in to mass update.
Warning: This only works if the contact has an email or company has a domain. If you attempt without unique values in email/domain; you will duplicate all your records!
Contact Report - filter for email is known
Company Report - filter for domain is known
Hope this helps and Good Luck!
That's how I would do it, Kanioma.
But even better would be if Hubspot added a feature to auto-format telephone numbers when entered. (I know this has been requested multiple times -- hopefully they'll get around to it soon!)