As Question :) Already have alchemy and herbalism on my main.
Typical good combo for Paladins is Blacksmith and Jewelcrafting. The extra sockets for wrist and gloves that you make are perfect for putting the Dragon's Eyes into
I'm running Mining and Jewelcrafting on my pally. Mining is providing me LOTS of gold for Lvl30, so it's great if you need a source of income
It really depends.
If you mean what professions are nice to have while leveling, I'd recommend something your Paladin can use. Blacksmithing for gear, or Engineering for toys/trinkets. Jewelcrafting is great but you won't have many gem slots while leveling, and you'll only need a handful of glyphs from Inscription. And if your main has alchemy, they can supply you with elixirs. If you do take one of these, Mining may be a good companion.
If you are looking for professions at 80, any of them will confer bonuses to you. Blacksmithing's sockets, or Leatherworking's bracer enchants, or Enchanting's ring enchants, etc etc, are all tuned to give approximately equal bonuses. So it comes down to which you'd like to try, which you may enjoy leveling, or which may give side bonuses you enjoy. Right now Engineering is popular because of all the cool things like item enhancements, teleporters, auctioneer in Dalaran, etc.
I assume you don't mean which professions will simply make the most money, since you mentioned your class. But gathering professions tend to bring in the most money, as long as you enjoy farming. Crafting professions only make lots of money if you are very shrewd and/or have some very rare recipes.
As an engineer I'm obliged to say Engineering.
If you're looking to min/max, Blacksmithing and Jewelcrafting are by far the best, with Engineering a little ways behind them. However, both of these are expensive professions, so if you dislike herb farming on your main to support them, you could swap one of them out for mining or skinning.
Whatever your profession choice may be, consider pairing it with the matching gathering profession. Blacksmithing/Jewelcrafting/Engineering with Mining would seem to be the best at first glance.
However if your aim is for endgame raiding the two best professions at this point are Jewelcrafting (for the Jeweler only Dragon Eye gems) and Tailoring for the embroidery (Lightweave, etc.). These two give the most dps and spellpower of all the professions.
If you aspire to tank on your pally, BS + JC is still BiS for tanks. No other profession combo provides the stat flexibility of those two, which is crucial for tanks that have to maintain minimums of 540 defense, 8% hit, 26 expertise, and a certain dodge:parry ratio.
Gather all the mats you need to powerlevel both (search the net for profession powerleveling guides if you're not sure what mats that requires), then drop your gathering professions and powerlevel.