In the latest metasploit version it won’t show “starting the payload handler”, so the message you have it’s ok.
Make sure that you’re using the same payload when generating the backdoor and when using multi handler, if you’re already doing that then try using a different port, if you’re still having issues then please show me the following please:
1. Result of ifconfig and route -n in Kali.
2. The result of ipconfig in Windows.
3. The result of options before generating the backdoor in Veil or the IP used in the backdoor.
4. The result of show options before running the multi handler.
5. Can you share a screenshot of the Network settings used in VirtualBox for both machines.
Let me know.