This appears to be a folk tale with little contemporary evidence of the event actually happening, but the tale itself does seem to date to the 15th century.
According to Volume 17 of the 1911 Encyclopedia Britannica, the tale is told in a few ways:
MACAIRE, a French chanson de geste. Macaire (12th century) and La reine Sibille (14th century) are two ...
A book, The 14th Century, seems to back the claim up somewhat, but places the duel earlier than 1400, during the reign of Charles V of France, which was from 1364 until his death in 1380.
The book in question, which is available from the Library of Princeton University, gives greater details and was written in 1869.
The relevant portion is reproduced here