Let's run with the starfish idea and build a hydra. Like a big reptile with many heads
A lot of these posts are approaching the problem backwards, and answering "how could an existing single-brained creature develop an additional brain" and that's an impossible evolutionary path - neural tissue is just too expensive and a semi-evolved brain would not be useful alongside their existing fully-evolved one.
We need to instead answer the question "under what circumstances would a non-brained creature evolve multiple brains" and the various starfish posts above spotted the solution - the answer is radial symmetry. Or basically any body layout in which it would make sense to have the sensing/processing apparatus (It's best to imagine the brain as a thing that evolves from the eyes - it is efficient to colocate them and they are made from the same type of tissue) located on an extremity, and not along a line of symmetry.
This seems quite unlikely to develop with bilateral symmetry, as the sensing/processing apparatus can at once be an extremity (the terminal end of the symmetry line) and place itself equidistant from the two halves of the organism, which feels like an efficient organism.
But this isn't so with the starfish... it would have to be very TALL for the centre to be a sensible place for a head... and it already has quite a lot of sensory apparatus on the tips of the arms, so this makes the tips of the arms a strong candidate for the development of additional processing tissue.
EVOLUTIONARY BONUS - evolution tends to flow more smoothly if it doesn't need to develop multiple systems in parallel... if each incremental new change is separately useful to the organism. And we get that with the starfish - it is already a radially redundant organism, consisting of identical modules. This means for this creature to evolve multiple brains it need simply continue to add processing tissue to the tips of its arms incrementally. It doesn't NEED to develop complex systems for coordinating between the brains - at least not right away! Whilst the ability to coordinate between brains is obviously useful; each arm being separately clever is also independently useful. This gives us a good evolutionary ramp, we can add intelligence incrementally and coordination will follow in it's wake.
We're still a squishy thing though
Alright so now what? We don't want a squishy boring sea creature. We want a cool interesting alien/monster. So where does evolution go next?
Well, now that the arms are specializing themselves into sensing/processing devices ("heads"), maybe we want to do more with the central body where our gut and reproductive organs live? Lets extend this mass at the base, and develop a "foot" like snails have, so we can bring our "arms" up off the ground and allow them to continue their specialization away from being a locomotion device and further into being our sensing/processing apparatus (much like how humans specialized our forelimbs away from locomotion and into manipulators).

So now we have something that looks a bit like a sea Anemone... we've got a foot for locomotion and organs we don't want extra copies of, and we've got a set of "braintacles" that house our sensing, processing and manipulator apparatus.
Let's step back. Where are we in the evolutionary history of the world? We're right near the start. The Ediacara. Bilateral symmetry has not achieved dominance and large carnivores do not exist yet - all life is squishy sea creatures feeding off plants and microbes in the water column or stuck to surfaces. They were simpler times, when evolution could try all sorts of wacky experiments without worrying about armour or teeth or speed, because there was nothing out there trying to eat you unless you were plankton.

Lets add a new feature for thriving in this environment. Most sea creatures (and we assume most Ediacarans) reproduce by spawning and and thus have a plankton stage... which as we mentioned a moment ago, is the only way to get eaten in this era.
So let's use our radial redundancy as an advantage to skip the planktonic stage.
Our organism now has two reproduction modes - sexual (spawning and creating planktonic larvae) and division (no sexual recombination, but we skip the planktonic stage and thus skip predation during the Ediacara). For coolness, let's imagine that each of our "braintacles" can seperate off from the main trunk of the organism, becoming a free-swimming snake-like creature.
So our lifecycle is plankton -> gets bigger to become braintacle -> fully matures to develop a trunk (housing a bigger gut and sexual organs) -> and then can both develop additional braintacles (making the organism more advanced and also allowing future reproduction by division).
This is a strong basic model. We now have a creature that can add additional sensory/processing capacity as it ages (the Elders are wise!), an individuals genome is likely to survive injury (if the trunk is damaged irreparably all braintacles can separate, disperse, and generate new trunks). And because it has 2 different reproduction modes that are optimized for different ecological conditions, it should be robust to major ecological upheaval.
Which is important, because the end of the Ediacara is coming.
The Predator Apocalypse
The first macro-predators emerge, and before "food chains" can properly become a thing almost everything just gets eaten. Almost all body-types are completely wiped out. But not our creature! Whilst they haven't evolved combat abilities yet (there was no reason to in the Ediacara!) they are well equipped to escape combat. Infact escaping is a reproduction event for our creature. So the predators come, trunks die and braintacles disperse... some of the braintacles survive long enough to grow a new trunk and spawn and... hallelujah. Because of the sudden predator-apocalypse, there are not many filter feeders left to eat our planktonic stage, and there is not much competition for food. Our creature has a population explosion, and achieves the population numbers it needs to evolve combat abilities.
And so the Ediacara ended, and all life that remained had teeth, claws, shells, bones, and other hard things for battle/predation. But our little many-brained creatures survived it, it's one of the fighty monster things in the food chain now. Infact, as one of the few creatures to survive the Ediacaran extinction event, it now diversifies and fills many ecological niches. It is one of the two dominant bodyplans of this world. It is the hydra bodyplan... and the only other major bodyplan is that of the first predator.
Fast forward to the Jurassic period of planet Hydra.
Our canonical example of the hydra bodyplan stalks the forest. It is a large many headed reptile. Each head sits atop a snakelike-neck, which in times of severe injury can separate from the main trunk of the body and become an independent snakelike organism. But the heads do not separate by choice. For when they are together they are smarter, they can pool their intellectual and sensory resources to better understand their environment. They can draw upon each others memories, most valuable of which is the oldest head, their leader and mother, the one which originally grew this trunk. And what a trunk! The claws! the musculature! The large digestive tract and sexual organs! In their Hydra form they are a lord of the forest, a powerful combat machine with prodigious intellectual abilities.
And should they fall from grace they shall become snakes. Separate. Weaker and dumber... but nonetheless whole. As snakes they can flee and hide, and grow. To one day become a Hydra lord once more.
And that is good... for a shadow crosses the sky... that which hunts the hydra is coming...

p.s. apologies for the necromancy on a 5 year old post... I just... I just love mad things like this...