In my experience, Mario is the natural secondary for Pac-Man.
With that said, I'm not as serious of a player as other people. My secondary (by time spent learning a character) is arguably Gannondorf or Robin. But whenever I pull out Mario, it seems to give players a bit of trouble adjusting right after a PacMan fight. PacMan and Mario really are polar opposites.
Robin is nice from an obscure point of view, as well as a very strong changeup to gameplay. Robin may be slow, but has extremely solid B-Reversals. Robin's micromovement is actually damn good due to ElFire and Thunder b-reversal shenanigans.
Furthermore, all of Robin's aerials can KO below 100% (especially UAir and BAir). Robin's Smash attacks are similarly slow as PacMan's (but hit a heck of a lot harder), and Robin's Jab-Jab-Jab (Fire) has virtually the same hit-confirm timing as PacMan. Robin's tilts are also roughly the same speed and range as PacMan's tilts.
Switching from PacMan to Robin is basically a study in mastering B-Reversals, the properties of the new projectiles, learning to "tilt" your aerials (to switch between LS-Airs and Bronze-Airs) and then mastering a new combo game. Robin has a hell of a lot to offer, including book throwing (Z-Drop combos and the like), double-El Fire combos. But when it comes down to timing DSmash, FSmash, or DTilt against a roll, Robin and Pacman have a good number of similarities.
---------------
Honestly though, I stick with Pacman and Robin because of the pun. (Get it? Its like "Batman and Robin"... except with Pacman. I'm so smart! jajajaja).