A saída de apt-cache policy linux-headers-4.4.0-24-generic
que você forneceu foi uma pista importante para a causa raiz desse problema. Como o comando relatou (em parte) Candidate: none
ficou claro que os repositórios não foram configurados corretamente em seu sistema e, portanto, não sabia onde encontrar o pacote desejado. Adicione http://us.archive.ubuntu.com/ubuntu/ trusty-updates/main
à sua lista de fontes e você poderá instalar o pacote.
Para que você possa verificar o resto da sua lista de fontes, aqui está o meu, para usar como exemplo (removi as linhas comentadas).
deb http://us.archive.ubuntu.com/ubuntu/ trusty main restricted
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty main restricted
deb http://us.archive.ubuntu.com/ubuntu/ trusty-updates main restricted
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty-updates main restricted
deb http://us.archive.ubuntu.com/ubuntu/ trusty universe
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty universe
deb http://us.archive.ubuntu.com/ubuntu/ trusty-updates universe
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty-updates universe
deb http://us.archive.ubuntu.com/ubuntu/ trusty multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty multiverse
deb http://us.archive.ubuntu.com/ubuntu/ trusty-updates multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty-updates multiverse
deb http://us.archive.ubuntu.com/ubuntu/ trusty-backports main restricted universe multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty-backports main restricted universe multiverse
deb http://us.archive.ubuntu.com/ubuntu/ trusty-security main restricted
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty-security main restricted
deb http://us.archive.ubuntu.com/ubuntu/ trusty-security universe
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty-security universe
deb http://us.archive.ubuntu.com/ubuntu/ trusty-security multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ trusty-security multiverse
deb http://extras.ubuntu.com/ubuntu trusty main
deb-src http://extras.ubuntu.com/ubuntu trusty main