Heres my experience with this problem:
I installed Kali Linux from a live memory stick. Whilst installing I didn't have an internet connection.
This meant that my sources.list file was set to "Default Off-line Install Values". This meant that when installing I was limited to just the packages and data from the memory stick I Initially installed from.
To fix this, you need to change your sources.list (called switching branches):
Open terminal:
nano /etc/apt/sources.list
This opens the sources file
Now at the top of the file paste in the following two lines:
deb http://http.kali.org/kali kali-rolling main non-free contrib
deb-src http://http.kali.org/kali kali-rolling main non-free contrib
Press CTRL + X then Press Y and Enter to save the file.
Now you can type the following commands to update Kali:
sudo apt-get update
sudo apt-get upgrade
sudo apt-get dist-upgrade
reboot
And finally, you should now be able to...
sudo apt-get install linux-headers-$(uname -r)
This is just my unique experience with this error stemming from an offline install.
I hope this helps someone else out there.
Reference
uname -a
? – Ahumadaapt-cache search linux-headers
. – Squamulose