Can I migrate storage domains, and thus all the VMs within that storage domain?

Or will I need to build new cluster, with new storage domains, and migrate the VMs?

Actually you can create a new cluster and ensure that the Storage domains are accessible by that new cluster.

Then to migrate, you just need to power off the VM, Edit -> change cluster, network, etc and power it up.

It will start on the hosts in the new cluster and then you just need to verify that the application is working properly.

Best Regards,

Strahil Nikolov