I'm more of a SK so I can't really help with some of these questions but here's some help/suggestions with some...
Soloing? Stay old world for as long as you can, most camps will turn light blue at 54 and doing those to 55 will take you nearly forever - until then though if you don't mind losing Freeport guard faction (East/West) I'd recommend the nobles camp in Highkeep on the 2nd floor. Respawns are quick enough, you can lull etc and they aren't connected to the wandering Isabella Cellus if your faction is okay with bards.
If you've got the plat I'd highly recommend the Deepwater BP, yes there is healing attached as a cleric would heal as he/she applies it to a group member - probably your biggest downtime minimizer.
Use your best DPS weapon whether its 1h or 2h. If it is 2h, keep a shield handy if you have casters - I never found bash to be that practical solo otherwise unless I was fear kiting (SK things).
Yaulp = +STR
STR = +atk rating
+atk rating = more dps (though probably not much more for a paladin)
Not sure if its worth it for paladins but rogues cap STR for max dps, run a parse if you're inclined and see if it's helping
[You must be logged in to view images. Log in or Register.]
Also if you are soloing wherever you are, donate for buffs if there's passing druids/clerics/shamans/enchanters... anything to give a smoother session is a helper I think.