O VMware Server era meio capcioso pra instalar, até as versões que usei. Depois passei a usar apenas o VMware Player ou o VMware ESXi, e nunca mais acompanhei o Server. Mas vamos ver o que dá pra fazer.
Acredito que o pacote "linux-headers" substitua o tal "linux-kernel-devel". Se não substituir, tente o pacote "linux-source", que é o fonte completo do kernel com os patches usados pelo Ubuntu.
Provavelmente você vai querer instalar também o meta-pacote "build-essential" [que traz, entre outras coisas, o gcc e o próprio linux-headers]. Se não ajudar, com certeza não vai te atrapalhar.