"The name NAS-HAdatastore already exists"
But wait, it does not exist on this host.
As it turns out, the error message is quite misleading - it should say something like - "This datastore is mounted with a different server:/vol/path/ options on the other nodes in this HA cluster - make sure they match"
Sure enough, the other nodes had the datastore mounted with a trailing slash (server:/vol/path/) and I was attempting to add this mount without the trailing slash.
Making the mounts consistent resolved the issue and gave me the 2 datastores I needed for functional cluster HA!