The root of the problem is that you’ve set the PDF logo as a PNG file type. The Zend Framework class that handles the PDF compilation doesn’t support de-interlaced images, which is a very common state for PNG file types.
The PNG file type in itself isn’t the problem, despite some of the solutions to this problem saying to convert to JPG. The problem is that the PNG isn’t interlaced.
There are two main differences between the two. Interlaced images increases the file size (bad). The benefit of de-interlaced images is that the pixels load in rows, rather than randomly (good). This is your typical image loading behavior; a slide-down effect.
This is compared to interlaced images where the pixels load randomly, which makes them blurry until fully loaded.
You can keep the PNG filetype by deselecting ‘Interlaced’ in PhotoShop and saving. If you don’t need the PNG file type, the easy solution would be to convert to JPG if you don’t have PhotoShop.
Finally, update the PDF logo inside Magento here:
Configuration → Sales → Sales → Invoice and Packing Slip Design