I just unlocked Paladin and I plan to go strictly melee... at least for a few climbs. If I am to go all-out melee, would the recommended build be the same as fighter/samurai?

yes. Try to get the same dex at least as the fighter and samurai and then stat rest strength

Personally I've heard diminishing return starts weighing heavily on you after 100 dex.

90 Dex it starts diminishing..by the time you get to 120 you don't wanna go any further

I experiment between 90 and 110

I've found 100-110 works best instead of 120