@fm22 Thank you for posting your question on Microsoft Q&A platform. Happy to answer your questions!
Is it possible that it's because of the location of the VM vs the location of services vault?
Short answer - YES!
The reason for slowness is definitely region as you are sending data across continents.
Is there a charge in transferring or changing the vault location? What would be the best solution here.
Moving Recovery Services vaults for Azure Backup across Azure regions isn't supported.
You can stop protection and retain backup data for MARS as well. See the instructions here -
Doc ref: https://learn.microsoft.com/en-us/azure/backup/backup-azure-move-recovery-services-vault
Does that mean I need to create a new recovery services vault with the new region location and run the backup from scratch?
YES!
If the response helped, do "Accept Answer" and up-vote it