Translation:Can I tell you a story?
It sounds a bit less natural to me but should probably still be accepted.
More common and perhaps more natural-sounding because of the shortness of "you", but arguably not really "more correct" as an English structure, I'd say.
MatchCheng's structure is particularly useful if the recipient requires a longer description, e.g., "He's been telling the story to anyone who'll listen."
Anyone care to translate that example into Chinese?
"I can tell you a story, do you want to hear it?" was rejected but I think it's also fine
I think (1) "可以...吗" refers properly to the question of whether the speaker can tell a story, (2) the "给你听" part means "to you", and (3) the "给你听" part is rather incidental, and isn't the fundamental referent of the "吗".
For your sentence, I would suggest a translation of something like "我可以讲一个故事给你听，你想听吗？"
If the grammar at https://resources.allsetlearning.com/chinese/grammar/Expressing_%22for%22_with_%22gei%22 is any indication, this usage of "給" precedes a target after which a verb or verb phrase must occur to describe what will happen to the target.
Does this earlier chain of comments help?
May I tell a story to you? May is asking for permission and can is asking if you are able...
Correct. However in common usage "can" is frequently used to mean "may"
It would be different meaning. If based on your explanation, it means 你要听一个故事吗？