The paladin's code says nothing about celibacy or not paying for sex, the only thing that's at all open-ended in the code is the "and so on" in the rule that the paladin must act honorably, and unless you believe that in all circumstances, patronizing a prostitute is inherently dishonorable, even if it does not contradict the tenets of your religion or break any oath you've taken, is legal in your society, and you treat the girls well and pay on time, I don't see Cedric as breaking the code here.
Is he a Marty Stu in a quasi-christian milieu? Maybe. The fiction was a mixed bag, I think the terms Mary Sue and Marty Stu get thrown around way too much these days, to the point that you can pretty much deem any protagonist who is a bit of a special snowflake to be one...and protagonists almost by definition are supposed to be special and interesting in a lot of cases. Look at some of the examples I've been mentioning, James Bond, Superman, Batman...beloved cultural icons, would definitely be decried as loathesome Marty Stus if they were made up by some random RPer on the internet instead of being famous iconic characters. But yeah, when Cedric's God depowers his own high priest for wanting to get rid of Cedric and things like that, it does get a bit grating...but on the other hand most of the fiction Shilsen came up with was highly entertaining and presented Cedric as a pretty balanced character. As for the other part...I think the emphasis here has to be very much on the QUASI in quasi-christian. Cedric's religion seems to be a bit more laid back in terms of the whole prudishness and piety business and more focused on "we help the helpless", a bit...Pelor-esque maybe? The High Lord definitely isn't uptight. I see Cedric as most likely an LG paladin of an NG deity, with most of his lawfulness coming from his personal mannerisms, his rigidly consistent, habit-driven nature, dedication to duty for the sake of duty, and scrupulous honesty, rather than the kind of lawfulness a more traditional paladin might have, which is more about trying to impose order and live by complex tradition and hierarchy. But as the SRD itself says, there's always more than one way to play a given alignment. And mind you, one of Shilsen's pieces of fiction explicitly says that the rules of Cedric's religion don't forbid, or in any way mention, prostitution, Magnus just thinks it's icky and surely must be disallowed (even though he has no actual basis for that belief in his religion's scriptures) because it goes against his glorious puffed up notion of a paladin as a perfect paragon of Galahadeyness...but hey that's what the saint template is for.
Long ramble aside though, being a marty stu in a quasi-christian setting is not actually against the paladin's code as written.