That one with STA508 can indeed work with up to 36v ... the absolute maximum is 40v.
The STA508 is a 4 channel amplifier - but each two channels are paired together as a single channel to simplify the design of the PCB.
Unfortunately, there's VERY LITTLE information in the datasheet regarding how many watts the amp can produce with minimal distortion - that figure of 100w could be with 10% thd which would be horrible.
Anyway, a 24v input would be enough for that amp to output some serious music power, probably about 2x60w ... but that means at about 80% efficiency, you would need about 150 watts to get those 2x60w.
The 24v x 5A would still work if you don't plan to get some reasonable volume at low distortions.
At 36v input, if I were to guess I'd say that amp can do about 2x80w with minimal distortions
But you'd need better cooling for such high power (for example put a 120mm to blow air over the whole board because that small fan and heatsink wouldn't be able to keep the amplifier chip cool at such high output)
The 36v power supply would be better and the 5.9a model should be enough, but if the price is only a few dollars more, I'd go for the 9a model, simply because it may have better heatsinks and won't be so loaded during use so the fan inside won't be as noisy as the lower end model.