You can just add an ESXi host directly to Veeam and then restore vCenter directly to the host. Once that's done you can boot up vCenter, make any adjustments, for example by removing/readding any rebuilt hosts, then start restoring other VMs. Of course, there may also be other VMs that are critical before you start vCenter (DNS/AD, etc.), but once again you could restore all of them directly to any ESXi hosts and then go from there.
For small/mid-sized deployments I don't even really consider vCenter all that important since it's really part of the infrastructure. I'd normally say most companies are more concerned with getting their business focused systems up and running so you could always just add multiple ESXi hosts directly to Veeam and restore all of your critical VMs quicky, then worry about vCenter later. It's really up to you, but Veeam is flexible enough that it doesn't really matter.
Of course, since you have Veeam, and you mention having local ESX host storage, another great option is to use Veeam replication to replicate those VMs to local storage, that way you don't even have to restore those systems, just failover/power on their replicas from the local storage.