Good analysis. I was disgusted at myself for taking the Parisian celebrity interpretation, then somewhat consoled but at the same time disturbed that on Hacker News of all places so many people did the very same. But I think you've hit the nail on the head with the title-case Pairs factor. The All Stars expression probably introduced some anchoring too.

Exercise to the reader - use the observed principals to concoct an equally misinterpretable headline.

The brain has multiple indicators for this misinterpretation. Stars early on in this sentence, narrows down context, Born in makes us even further think of a human star aka celeb, Pairs is capitlized, making us think it is a proper noun, the brain also doesnt read the middle letters of words if you remember that word jumbled experiment where you can still read it. All of this combines together to make the brain on first glance say Paris and not pairs

Isn't it the capitalization of the first characters of each word which causes the confusion?

New evidence that all stars are born in pairs

versus

New Evidence That All Stars Are Born in Pairs

I've never understood the rationale of capitalizing headlines this way anyway (is it the American way?)