The story
Attested since 1936, originally in American English. Possibly from cakewalk, or the notion of facility that derives from many cakes having agreeable tastes, and hence being ‘easy’ to consume. Compare French être du gâteau (literally “to be a cake”), être de la tarte (literally “to be a pie”), both meaning "to be easy, to be a piece of cake".
Etymology from Wiktionary, CC BY-SA 4.0.