How to suppress terrible noise from MAX7219?

Consider attacking the problem at the noise generator end, i.e the LED driver IC, not on the audio end.

One obvious suggestion (which you've probably addressed already) is to add decoupling capacitors to the MAX7219, as close to the power pins of the IC as possible. Also, since the current drawn by this IC jumps drastically as it multiplexes, it might be best to add two capacitors, a small value typical decoupling one as is always recommended, and a higher capacity electrolytic one (try 10 or even 100 μF) in parallel, between the Vcc pin and Ground.

If this too does not address the problem, it might be worth plugging a small, very low-resistance inductor into the power rail going into the LED driver: No specific reference I can quote for this, but I've used this method for noise suppression with a TLC5940 LED driver IC, using a 22 uH inductor I had available, connected between the positive side of the electrolytic cap that is tied to the power rail, and the Vcc pin of the IC which is tied to one pin of the lower-value decoupling capacitor. Thus the inductor sits between the positive pins of the two capacitors.

I will try and add a schematic later, if the explanation above is unclear.

Depending on your success with the above suggestions, please comment, in case other suggestions come to mind.