The 28/3.5 lenses are generally considered to be superior to the larger aperature (2.8, 2) ones. I think generally the "K" would be the most desireable in K-mount, while for M42 mount the SMC Takumar would be considered best, they're essentially the same lens in a slightly different package. "M" is also supposed to be very good, I think (it's considered) slightly better than the "A". I haven't really heard that any of the M42's are bad, but that's just from reading online. From experience all I have used is the K 28/3.5 and it is excellent to be sure.
While I'm sure it's possible descriptions I've read of using the converters didn't sound to pretty, I would be very sure of what you're getting into before going that route. ie. to remove a lens you have to first unscrew the lens, and then use some sort of a pen or a tool to remove the adaptor. Maybe it's easier going the other way, I don't know.
Dave