Why not remove the PAE kernels along with their headers? You don't use them anyway, and that will both solve the updates problem and free some space. To do that, use the following:
This command will only show what's to be removed, without removing anything.
dpkg -l linux-* | awk '/^ii/{ print $2}' | grep -v -e `uname -r | cut -f1,2 -d"-"` | grep -e [0-9] | xargs sudo apt-get --dry-run remove
This command will purge all unused kernels and headers.
dpkg -l linux-* | awk '/^ii/{ print $2}' | grep -v -e `uname -r | cut -f1,2 -d"-"` | grep -e [0-9] | xargs sudo apt-get -y purge
Info source
Edit: Apparently, that command doesn't remove the metapackages, so I'd add the follwoing as well:
sudo apt-get purge linux-generic-pae linux-image-generic-pae linux-headers-generic-pae