What is your current team and why?
In generell I think Paul is better as second character and is particular good for zoning teams as a switch cancel or crossrush into him means a huge distance gain due to phoenix smasher (e.g sagat uppercut SC, or guile flash kick SC, sim crossrush etc).
Paul is not a team player tho, he is build around himself with link combos overshadowing cross rush combos most of the time and having no real solid way to make use of switch cancel. he is good to tag into, but not to tag from.
He also lacks zoning game, why I think he needs a character that can deal with that, making a zoning character on your own, again, a reasonable option as partner.
After testing through a good bunch of characters I’m settled down on guile (till cody arrives that is). it great to have guile on front, zoning and building meter, while switch canceling / cross rushing into paul for damage and distance makes guile even better and guile has a very good cross rush (c.mk, s.hp, h). paul has also a very good corner pressure game, with a huge reward game out of nearly anything, where guile usually lacks good options.