Acho que meu problema está resolvido.
A razão é que o tutorial para instalar o kernel 4.16 apenas me disse para instalar:
linux-image-4.16.0-041600-generic_4.16.0-041600.201804012230_amd64.deb
linux -headers-4.16.0-041600_4.16.0-041600.201804012230_all.deb
Caixa do Virtualbox perdida:
linux-headers-4.16.0-041600-generic_4.16.0-041600.201804012230_amd64.deb
Depois disso, eu consegui fazer corretamente:
sudo /sbin/vboxconfig
e funcionou perfeito:)
Eu tento instalar uma nova VM e um antigo OVA para dizer se ele funciona corretamente