Just downloaded VirtualBox. Performed almost exactly the same series of steps (VirtualBox can boot from the ISO so no need to change the extension to HDD and I’m not sure what to pick under the hypervisor settings) and it worked immediately on the first attempt.
Meant to mention, not long after the release of beta2 I was able to get a running Parallels VM with Haiku without any huge struggles. So I think Parallels have changed something.