Hey guys I was having problems just like many installing vmware on kali. Although there are many posts and solutions non worked for me accept this one. I hope this solves most of your problems which I decided to share. Thanks and hope it works!

1. Make sure you got these sources listed in your /etc/apt/sources.list (I had only one but not the other which was my problem)
deb http://http.kali.org/kali kali main contrib non-free
deb http://security.kali.org/kali-security kali/updates main contrib non-free

2. Only after you can update and upgrade
apt-get update
apt-get upgrade

3. Now you can successfully install the headers without getting the "package not found error". I used the following command:
apt-get install gcc make linux-headers-$(uname -r)

4. This should successfully install the headers and now you can install vmware successfully

Hope this helped guys if you have any problems let me know I'll get back to you. Thanks!