I first repaired package state with dpkg and apt-get -f install.

Then i tried to remove old kernels as suggested via apt-get autoremove.

But this would only remove one kernel. There where many more installed that i found with

dpkg --get-selections|grep linux-modules|grep -v deinstall

I had to explicitly remove those kernels:

apt-get remove linux-image-4.4.0-1123-aws linux-image-4.4.0-1121-aws linux-image-4.4.0-1119-aws linux-image-4.4.0-1114-aws ... linux-modules-4.4.0-1124-aws  linux-modules-4.4.0-1121-aws linux-modules-4.4.0-1119-aws linux-modules-4.4.0-1114-aws ...

Afterwards i could clean up using apt-get autoremove which removed headers.

Some leftovers where reported so i had to clean them manually:

cd /lib/modules
rm -rf 4.4.0-1124-aws 4.4.0-1123-aws 4.4.0-1122-aws 4.4.0-1121-aws4.4.0-1119-aws 4.4.0-1118-aws 4.4.0-1117-aws 4.4.0-1114-aws ...

I still don't know why apt-get autoremove didn't work for me.

I automated removal of the unneeded directories with this shell code:

sudo apt-get autoremove
cd /usr/src
sudo rm -r $(comm -23 <(ls /usr/src) <(apt-file search /usr/src/* | awk -F / '{print $4}' | sort -u))

The last line deletes every directory that is present in ls /usr/src but is not present in a list of owned files in that directory. The command ended up deleting all but the most recent directory. Before running for real, I suggest changing rm to echo rm to see what would be removed.

This command worked for me:

 apt-get -f autoremove

Context

I was getting the same error as OP. To be able to run the command suggested in jpereira's answer (apt-get -f autoremove), I first had to free about 10MB of space.

But when I ran it, something weird happened where apt-get said it was going to remove all the linux-headers (and some other) packages, but it first tried to install another package (snapd), but because there was no space to install it, the process failed.

The next time I tried running the command, it was as if apt-get had forgotten about the linux-headers (and the other) packages. So I went ahead and attempted a manual removal of one of the packages:

sudo apt-get remove linux-aws-headers-4.4.0-1065

This command, successfully removed 2 directories from the /usr/src directory. It removed the directory with the same name as the package and the package of the same name but with the -aws moved to the end.

To remove all of them I ran this command, BUT DO NOT USE IT because I ended up removing some packages that would have not been removed by the autoremove functionality and I also did not remove all the packages that would have been removed by the autoremove functionality.

cd /usr/src
while read pkg; do sudo apt-get -y remove $pkg; done < <(find . -maxdepth 1 -type d -name "linux*" -printf "%f\n")

Recommended Solution

The perfect solution would have been to run the following commands, but you first need to copy the list of modules that autoremove initially said that it was going to remove:

echo "<PASTE COPIED LIST OF PACKAGES HERE>" | cut -c3- | tr " " "\n"

Make sure that the output of that command is a list of the packages where each package is in one line. If that works, then go ahead and run something similar to the command I used before:

while read pkg; do sudo apt-get -y remove $pkg; done < <(echo "<PASTE COPIED LIST OF PACKAGES HERE>" | cut -c3- | tr " " "\n")

More context

Running the recommended solution (after running the not recommended one) was also good for me because that removed some linux-image and linux-modules packages that were also occupying a lot of space but somewhere else!

The first command (not recommended one) freed about 3.7G of space and the second one (recommended one) freed an additional 1.7G. However, if you first run the recommended command, that command alone should free all the space that needs to be freed.

To delete linux headers safely, always use:

$ sudo apt-get autoremove

Sometimes the above command can give error like this:

Reading package lists... Error!
E: Could not create temporary file for /var/cache... (28: No space left on device)
E: The package lists or status file could not be parsed or opened.

In this case, delete one or two old headers manually. To do this first go to /usr/src folder and list the files according to date (oldest last) using below command:

$ cd /usr/src
$ ls -lt

Then choose an old header (e.g. linux-aws-headers-4.4.0-1067) and delete it using this command:

$ sudo rm -r linux-aws-headers-4.4.0-1067

After doing this, the command sudo apt-get autoremove should work without any problem.