Por que não remover os kernels da PAE junto com seus cabeçalhos? Você não os usa de qualquer maneira, e isso resolverá o problema de atualizações e liberará espaço. Para fazer isso, use o seguinte:
-
Este comando mostrará apenas o que deve ser removido, sem remover nada.
dpkg -l linux-* | awk '/^ii/{ print }' | grep -v -e 'uname -r | cut -f1,2 -d"-"' | grep -e [0-9] | xargs sudo apt-get --dry-run remove
-
Este comando irá limpar todos os kernels e cabeçalhos não utilizados.
dpkg -l linux-* | awk '/^ii/{ print }' | grep -v -e 'uname -r | cut -f1,2 -d"-"' | grep -e [0-9] | xargs sudo apt-get -y purge
Edit: Aparentemente, esse comando não remove os metapacotes, então eu adicionaria o seguinte também:
sudo apt-get purge linux-generic-pae linux-image-generic-pae linux-headers-generic-pae