The game should procedurally generate some mythical creatures every world, preferably assigning them to both particular civilizations as well as to particular regions. Once the game has the capability to procedurally generate creatures some, but not all, of them should actually be generated each game.
Even before they can be real, generated mythical beasts could be the basis for stories and traditions in a culture, with people in certain regions having generated stories about a local historical figure meeting one of the creatures. There could also be stories and traditions about how to protect yourself from one or another type of powerful mythical thing. Superstitious Dwarves should do things required by these stories, so you can get some insight into cultures and personalities. Adventurers should also be able to adopt superstitions, and either be seen as superstitious or just a rube if the local stories are thought of as more of a joke. Maybe superstitious people will appreciate each other a bit more, so if you show up to a house wearing the traditional peacock bone earring of evil critter repelling and the homeowner also has one on, they'll be more likely to let you stay the night.
Once there's a way to actually put the generated creatures in they should have actual warding methods corresponding to the stories. That way you might be the laughingstock of one village for doing the dance you were told would repel the local critter, but the next village over turns out to really have a nigh-unkillable beast that roams the forest at night and the talisman that repels it is taken very seriously. These shouldn't necessarily be dependent on whether the creature referenced actually exists in game necessarily. Sometimes a lot of fake stories should generate and people should just all be convinced from having a cousin's cousin that saw the thing in a fake story. Sometimes creatures should be very stealthy, reclusive, or not leave any evidence of their kills, so even though they exist nobody really believes it.
People could also spread fake creature stories around. Even if they do exist somewhere in the world they might not be near everywhere stories are told, and could be thought of differently all over. If there were a way to determine if a story is popular in a culture, or spreads to a degree, new false stories should be generated with historical figures in that entity/region/civ so Goblins aren't afraid of something they've only heard of attacking Dwarves.