I find this answer the most explaining, yet it's missing one thing.

People speak like, predators can learn what to eat and what not to eat, like with taste. But it has nothing to do with this. Because, the learned experience cannot pass to new generation. It would require the poison to be non-fatal, and the species of predator would have to be intelligent enough, so they could teach it. And still, some variants of predators might just try and like the experience, due to having mutations on their tasting receptors. So, how did they co-evolved?

Probably, once upon a time, predators who hunted those creatures varied by their instinct or senses of hunting creatures with specific shapes or colors, and those who liked eating colorful things died more and more often due to colorful preys containing more and more fatal poisons. This led to survival and production of those more who don't prefer eating colorful preys, and those who are more colorful "preys" (they are actually not preys anymore at this point).

Yet, time to time some mutations can give arise to the old variants of predators who liked to hunt colorful creatures, but they would keep dying, so their population in the pool would be neglected. On the other hand, if some mutations would create a "prey" that are colorful yet not poisonous now, it might increase its number in the genetic pool easily for at least some time due to predators not eating them anyway. But such mutations must be rare, and variants on the predators' side might eventually balance things back to this current state.

So, it may have a secret wave function in the background, which, things tend to converge towards this current state every time they deviate a little, rather than going the opposite direction, due to the path on the opposite direction being way longer compared to the current state of things (that is colorful being fatal). So, things must have been kinda locked down into this state.

Last but not least, it's amazing how it's not even about only one species of prey and one species of predator, but among many species of preys and predators. It must be due to many species hunting the same prey, and many species being hunted by the same predator.

By the way, everything above is kind of my prediction of how things happened and keep happening.