Groundbreaking Scientific Experiments, Inventions, and Discoveries of the Ancient World, (2003), pp. 27~28 (partially viewable at Google Books) by Carolyn A. Krebs suggests the 4th century A.D. as the likely time of the invention (in Asia).  Obviously, the finds mentioned for Roman and Etruscans horseshoes effectively contradict this.

Salima -- The received or traditional opinion is that the horseshoe
doesn't come along until Attila the Hun, i.e. early Medieval. However,
there is a shoe from good Roman context from a site near Newcastle, and I
also know of some others with good Roman context (which are unpublished as
yet). I think, given that the Romans were positively geniuses in the
working of iron, and also that I've seen some Roman nails that have the
peculiar one-sided form required for nailing the horseshoe on without
quicking the horse, that the Romans most certainly did use nailed
horseshoes as well as hipposandals.

This would also be true of mules; mules are in fact more likely to have
been shod than horses, and one of the shoes of which I am speaking above
was clearly for a mule and not a horse (the shape of the hoof differs).
Donkeys, however, I think are the least likely of the three equine
domesticates to have been shod -- anywhere, or at any time. If you have
small, U-shaped (rather than C-shaped) shoes they are probably for small
mules rather than donkeys. -- Dr. Deb