You'll definitely want to unlock Paladin once you reach 30.

If you're just (for now) going as far as 15 for the Paladin unlock requirement, Your CNJ class quests and hunting log should pretty much get you there. There's also some low-level sidequests in and around Gridania you probably didn't finish while leveling GLD in Ul'dah, so you could throw in those as well, or add a few FATEs.

You'll be getting double XP on mob kills just for having another class at a higher level, plus another 30% if you wear the ring from the Novice Hall training, and more if your FC offers the XP boost. With all those XP boosts, the first few levels go pretty quick, and you won't have to look too far to find enough experience to get to 15.

Then, if you come back later to level it further, past 15 you'll have dungeons, and those (especially through leveling roulette) give tons of XP.