For an Ubuntu 12.04 LTS system, you are running quite an old kernel. The current generic PAE kernel version in Ubuntu 12.04 LTS is
3.2.0-24-generic-pae. The generic PAE kernel version that came with 12.04 LTS when it was first released was
3.2.0-23-generic-pae. The kernel you're currently running is not provided in Ubuntu 12.04 LTS at all, which is why you cannot install headers for it. Your currently running kernel is from a previous Ubuntu release.
Unless you need to run such an old kernel, you should just use a newer kernel, and that will solve the problem. If you install the
linux-image-generic-pae package, you'll get the latest stable kernel for Ubuntu 12.04 LTS. If you install the
linux-headers-generic-pae package, you'll get the latest headers. As you receive updates, both the kernel and headers will be updated for security and stability, and they will always correspond to each other (so the headers package will enable the compilation and installation of kernel modules for the kernel provided by the image package).
If you find that even with that installed, you are booting into the old kernel, then you may need to modify your GRUB2 configuration. If this happens, please provide details in your question.
If you need to run this very old kernel, please also provide details about what you need this for. For example, did you have to manually select this old kernel to boot successfully?