Well, no-one knows for certain where he was born.
I think though that considering that the Frankish Empire lends more of its name and history towards the creation of modern France than it does to modern Germany, despite the Franks having originated in Germany, then it makes some sense to associate Charlemagne with France.
While we're here, have a picture of a descendent of Charlemagne dressed as Charlemagne:
