A story is usually ordinary, believable, interesting only to the extent you care about the characters or the happenings in it. A legend is bigger than that. It lasts, it is passed down, and as it passes from mouth to mouth it shifts a little. "This chair was made by my great grandfather for his first child and has been with us ever since" is a story. "This axe is the one my great grandfather used to clear this land and build this house" is more epic, but still just a story. "This axe is the one Eric, from a time before my great grandfather, used to kill seven wolves in a single night, we keep it over the table in the council hall to remind us of his bravery" is getting on to legend. When the wolf story gets longer, more dramatic - perhaps a few dogs or even children are taken, then night after night the pack is circling the village howling, no-one dares travel alone even in daylight, children are growing thin because nobody can go to the next village to trade for food, "until one night brave Eric hoists his axe, the only weapon he has, and..." now you're headed to legend. A legend can be inspired by a real story, but that brave team of three becomes just one person who can personify the bravery (or the intelligence, innovation, loyalty, faith, obedience, etc.) The work of an entire season now happens in one night. The recognition of the feat is immediate. And so on.
A legend has to be physically plausible though. If Eric is 40 feet tall, or that mountain was formed when a spirit lay down to rest because it was happy with the way people were turning out, or a single woman's anger burned that pass between the mountains, then you're into the myth zone. You can have myths, but if you want legends it has to be believable that a single man outperformed the steam-powered machine that was supposed to beat him or that one child's words ended a war or whatever.
Legends should also be sparing with details other than those that matter. Nobody can remember what colour Eric's eyes were or the names of his children, but the words he said when he came back with the wolf pelts, those are famous. Or perhaps the number of lace-holes in his boots. One or two tiny details make the legend shine, especially when surrounded by a vague fogginess about how old the person was or what they usually did.
In a story, the best legends are incomplete because the characters know them. Just as we might refer to the boy who cried wolf without telling it on the spot, a character can say "oh, look who is Eric of the Axe now" when somebody considers using an axe as a weapon, or says they will save the village, or whatever. You could do that a few times before a small child or someone new to the world asks to be told the story. That way the reader feels like they know part of it before they even hear it.