Having just glanced at the specs for these machines, any would be suitable really. I run Adobe Photoshop CS 8.0 on a slower PC than that, and Photoshop is similar to Paint Shop Pro. The ones I looked at in the superbudget section had Athlon 64 processors and I think 512MB RAM, which I think would be fine.
I'm no expert on Paint Shop Pro or photo editing, but I don't think you would have much of a problem with one of these systems. - somebody please correct me if I'm wrong though! What I mean by that is, it may depend on what you want to do with Paint Shop Pro, but I'd imagine those specs could pretty much handle everything.