I think you have answered your own question.
I view Legumes as an order of magnitude less harmful than (gluten) grains. Having said that, you have to decide if your approach to Paleo is
1) Is there proof this is really bad for me and absent such proof, can I continue to consume?
2) Is this essential from a nutritional point of view and are there no substitutes that are either less harmful and/or actually beneficial.
I think the divisions we see in this community regarding things like legumes, dairy, etc have to do with a bias to #1 vs #2.
Welcome to the community. Watch out for the genital-obsessed individuals trolling around here!