Is removing old linux-headers and linux-image packages safe?

Yes, it's safe.

And here's how to determine the answer for yourself using the uname command:

$ uname -r
4.15.0-34-generic

In this case, you can see that my running system is 4.15.0-34, several versions above -29. So if my hardware works properly on -34, then -29 is safe to remove. Ubuntu retains older kernel versions so that you can still boot your system in case a new kernel causes problems (it's very rare, but has happened)

Let's take a step back and look at the proposed removals a bit more carefully:

linux-headers-*
linux-image-*

image packages are what your system runs - they are binaries. Those are the important ones.

header packages are used to compile kernels and modules. They are not executable, and can be removed at any time.

Finally, let's explain what's going on under the hood: There is some package-management magic, and a really clever script tying it all together.

Apt manages your kernel images using a metapackage, typically the linux-image-generic metapackage.

When a new kernel is released, the metapackage is updated with a new dependency, and apt downloads that new dependency (the new kernel package).

A post-install script triggers GRUB to update and for you to get that "you should reboot" notification.

Another post-install script marks some (not all) older kernels as eligible for removal.

The next time apt runs, it notices that those older kernel packages are orphaned and eligible for autoremoval, and tells you so.

Ubuntu has used that post-install script to mark older kernel packages for quite a few years now, with great success. It keeps the newest kernel, and the currently-running kernel (just in case), and sometimes one older kernel. The script keeps your /boot from filling up with lots of old images - one image can be over 300 MB! On space-constrained, LLVM, and encrypted systems, /boot is often a separate partition, so keeping that space free is important!

Yes, Michael - it is completely safe to remove this old kernel. By default Ubuntu keeps two kernels - the current one and the one before. One set of kernel packages uses about 335 MB disk space and that's why you receive the information about the freed space. To completely remove those old kernel packages, including all configuration files, execute this command (purge instead of autoremove) :

sudo apt purge linux-headers-4.15.0-29 linux-headers-4.15.0-29-generic linux-image-4.15.0-29-generic linux-modules-4.15.0-29-generic linux-modules-extra-4.15.0-29-generic

I will explain how Ubuntu manages kernels before attempting to answer your question.

APT will always keep only the 2 latest kernels installed in your system. Ubuntu runs on the latest kernel and keep the other for backup.

For example, consider you have 4.15.0-29 and 4.15.0-33 currently installed. The latest will be activated by default unless you modified your grub. So you would be running Ubuntu on 4.15.0-33 and 4.15.0-29 is left for backup.

When you install a newer version, for example, 4.15.0-34, with apt upgrade apt will see that there now 3 versions in your system and mark the oldest one as "no longer required".

Since you weren't running your Ubuntu on that kernel anyway before you upgraded, it would be pretty safe to remove the old kernel with sudo apt autoremove as 4.15.0-33 would now become the backup.

Tip: You can add --purge to the command to completely remove the old kernels and not leave any traces and save even more space.