I don't know what Path of Legend is, so, uh. I don't really see S'sebek as the sort who'd go jumping through hoops (literally) for recognition, though. But if that's what it takes to make it work...
When I made S'sebek, I think the only character that was already backgrounded and stuff was Targ. I figured that at some point while he was fleeing North from Zangala (and up towards Ambria) he might've run into Targ - they've got a similar sort of outlook, from what I've read of Targ (saving people who can't help themselves, mostly), and I could picture S'sebek and Targ banding together. A less-than-smart ogre with a tendency for being crazy strong alongside an introspective sort could work out pretty well - and from there, the party could continue to form as others are encountered.
Of course, throwing everyone together at some sort of obstacle course is probably a lot easier to handle and stuff, so I guess that works, if it's what people like.