I understand that I need bring down all of the hosts in a cluster in order to enable EVC.
No, you need to bring down all VMs, not hosts (ESXi).
Could I vmotion all of the VMs hosted on a cluster to another cluster in preparation, bring down the hosts, enable EVC, bring the cluster up, then vmotion the images back to the cluster?
The problem is if you need to set an EVC mode on the cluster which is more restrictive than the native hardware provides. In this case, even if you vMotioned those VMs off to another cluster, you wouldn't be able to vMotion them back because the instruction sets they had when powered on are suddenly no longer available. Also, if you attempted to vMotion them to another cluster which was as restricted as the EVC level on which you wanted to set the source cluster, that too would fail. So in these cases, you really have no other options but to shutdown all the VMs to enable EVC. If on vSphere 6.7, you may be able to lessen the impact to some degree (in exchange for administrative overhead) by using per-VM EVC.
