"Embroider" is a verb meaning "create embroidery", a delicate, artistic form of sewing. Embroidering is sewing. When it is used about a story, it is a metaphoric use of a sewing term; it means "make the story sound fancy, the way embroidery looks fancy".
"Embellish" can refer to decorating physical things, but its other meaning "dress up a narration with fictitious matter" has been a part of English since then 1500s (etymonline.com). It isn't a metaphor.