I mean, if trying to reproduce a paleolithic diet was a good idea, then why stop at it? Why don't also try paleo healthcare or paleo housing?

I can think of at least one obvious answer to this question. Was it supposed to be rhetorical?

Modern medical and housing technologies are dramatically superior to ancient ones. A modern house is a better place to live than an ancient dwelling in quite a lot of ways. Modern technology gives us the ability to produce much more food than the ancients did, but it is unclear that the food is superior: nutritionally, modern foods do not have obvious and dramatic advantages over ancient foods (in many cases it's the same food!), certainly not to the same degree modern medicine can outperform ancient herbalism.

(This is not by itself sufficient to justify the idea of a paleo-like diet. That specific criticism just doesn't hold up.)

"look and feel of science" is a defining characteristic of pseudoscience.

I don't agree. Most pseudoscience is created by and for people who don't understand science.

Do the authors estimate these "priors" using some reliable methods It's more like if something has been consumed by our ancestors for millions of years it's probably healthy, although we are willing to let data change our position on this, or breast milk is the perfect food for babies and given how babies differ from adults we guess we probably need to make this adjustment...

Science and engineering work and have given us stuff much better than what our paleolithic ancestors had. In contrast, the field of nutrition has not succeeded in giving us a better diet than our ancestors ate.

From what I understand, hunter-gatherers eating traditional diets have very low rates of cancer, heart disease, strokes, diabetes, and obesity--the so-called diseases of civilization. The goal of many paleo people is to take the best of the paleo and modern world.

The rapid growth of obesity in the modern world shows that something is seriously wrong with modern diets and going to a paleo diet, which evolution conditioned us to for millions of years, seems like a safe alternative.

The big insights of paleo movement are that:

(1) evolution didn't have enough time to adapt us to a diet with lots of sugar and/or grains, (2) archaeology of graves shows a reduction in average health shortly after a community switches from hunter-gathering to agriculture, and (3) many people seem to get a lot healthier after going paleo.

I think yes to some extent.