Se você ainda tiver muitos pacotes de linux-headers* instalados em seu sistema, tente essa abordagem simples para remover cabeçalhos antigos:
dpkg-query -f '${binary:Package}\n' -W linux-headers\*|xargs apt-mark auto
apt-mark manual linux-headers-generic
apt-get -f autoremove
Se minha suposição estiver correta, de alguma forma você terá seus cabeçalhos marcados como instalados manualmente e isso impede que o sistema remova esses pacotes. Por exemplo, você instalou diretamente os pacotes, ou seja, pediu para instalar a versão exata do pacote de cabeçalhos do kernel. Os comandos acima tentam marcar todos esses pacotes como instalados automaticamente e fazer as coisas funcionarem conforme o esperado.
Se por acaso os pacotes já tiverem sido removidos, mas as pastas ainda persistirem e tiverem apenas algumas sobras dentro, isso significa que esses arquivos não pertencem ao pacote. Isso evita que o apt remova o diretório principal ao desinstalar o linux-headers* package. Você deve remover os arquivos manualmente neste caso.
Trivia : o recurso autoremove do apt funciona apenas para pacotes que foram instalados automaticamente. Isso significa que o pacote deve ser literalmente marcado como 'instalado automaticamente' e não deve haver pacotes que dependam dele. No caso do kernel do linux e seus cabeçalhos, temos este cenário comum:
- há um ou vários meta-pacotes como
linux-generic,linux-image-genericelinux-headers-genericque normalmente são marcados como instalados manualmente - existem muitos pacotes 'reais' com arquivos dentro como
linux-image-4.8.0-45-generice meta-pacotes dependem de alguns desses pacotes; estes são geralmente marcados como 'instalados automaticamente' - quando o meta-pacote é atualizado, normalmente requer versões mais recentes do pacote 'real' e, portanto, novas versões estão sendo instaladas
- os pacotes marcados como 'instalados automaticamente' só podem ser executados automaticamente quando não houver um pacote instalado manualmente que dependa dele, portanto, quando novos pacotes forem instalados, os antigos poderão ser removidos automaticamente mais tarde, porque ninguém mais depende desses pacotes.