Maybe a bit tricky to pick a single solution without knowing the circuit, but there are definitely things to try and you're definitely trying some of them. Do you know if they're in proximity of an AM radio antenna? It could be that the fix you've tried is fairly effective, but the signal strength near them is much stronger and it just isn't sufficient.
If you're hearing the radio, somehow the signal is finding its way into the amplification path, and because all you need is an envelope detector to demodulate AM, the parts required are often already part of amplifier circuits. A low pass filter (ferrite with a few turns) on the input signal line, you can make it fairly resistant to picking up radio signals, but since AM is a lower frequency than FM or TV signals, you will need more turns (more inductance) to have the same effect. A bunch of turns around a ferrite on the signal input, close to the amplifier device should be the most effective in terms of keeping the radio signals out of the signal going into the device.
Good grounding is also a critical step, making sure that both device's grounds are at the same potential and have a low impedance path to earth will go a long way towards helping and preventing chassis from acting as their own antenna or whatnot. Shielding the signal cable is a good reaction, but rather than cat5 or similar, I'd probably look at shielded XLR cables or something - something with a shielding braid or foil with a good connection to ground should dramatically reduce what's picked up on the signal cable, and a lot of 3.5mm connector cables aren't shielded. If it's a mono signal, almost any kind of coax could do the job so long as the connectors are easy to deal with.
I doubt caps at the PA output will help. While caps (effectively a low pass filter) could be potentially a benefit on the input, by the time the AM signal is in the audio band (demodulated) and is audible, the frequency content is already too low to be filtered out without effecting sound quality - so any filtering of the audio signal of the AM would have the same effect of the intended audio signal of the PA. It's going to be much easier to deal with the spurious signal before it's demodulated, when it's up around 1MHz and well away from the audio band. To that end, a small cap between the signal and ground of the PA's input could actually be useful for filtering, but if there's enough signal picked up on the ground wire as well (if the grounding isn't good), the signal won't be filtered out because it will be differential across the two connections. The actual value of the cap would depend on the source impedance of the input signal, but something in the ballpark of 10s of nF is where I'd start if I were to try.
Maybe there are some more audio/radio types that can offer more specific solutions that have worked for them.