I don't think there are any definite answers. I've drawn together what canon information I can find, and added my own speculation.
Probably in the BC era, but it's not clear exactly when. The original wand probably bears little resemblance to the modern device, but the key aspects would be the same.
In Philosopher's Stone, when Harry visits Ollivander's shop, he learns that the family have been making wands since the 4th century BC:
The last shop was narrow and shabby. Peeling gold letters over the door read Ollivanders: Makers of Fine Wands since 382 BC. A single wand lay on a faded purple cushion in the dusty window.
It's likely that wands were in use before this date, and Pottermore backs this up:
The family of Ollivander has long been associated with the mysterious profession of wandcraft. It is said that the name means 'he who owns the olive wand', which suggests that the original Ollivander arrived in Britain from a Mediterranean country (olive trees not being native to the UK). Mr Ollivander himself believes that his earliest forebears in this country arrived with the Romans, and set up stall (subsequently shop) to sell to ancient British wizards whose wands were crude of construction and unreliable in performance.
However, the Roman conquest of Britain only began in AD 43, some four centuries after the Ollivander family opened shop. It's not clear how these timelines match up. Still, it puts an bound on the latest that wands could have been discovered and used.
There are suggestions in Pottermore than Ollivander invented the wand “as we know it today”
Prior to Mr Ollivander's proprietorship of the family business, wizards used a wide variety of wand cores. A customer would often present the wandmaker with a magical substance to which they were attached, or had inherited, or by which their family swore (hinted at by the core of Fleur Delacour's wand). Mr Ollivander, however, was a purist who insisted that the best wands would never be produced merely by encasing the whiskers of a favourite Kneazle (or the stalk of a Dittany plant that once saved a wizard's father from poisoning, or the mane of a kelpie a witch had once met on holiday in Scotland) in the customer's favourite wood.
The best wands, he believed, had cores of immensely powerful magical substances, which were expertly enclosed in specially selected and complementary wandwoods, the result to be matched to an owner with whom the wand itself felt the most affinity. While there was initially substantial resistance to this revolutionary way of crafting wands, it swiftly became clear that Ollivander wands were infinitely superior to anything that had come before. His methods of locating wand woods and core substances marrying them together and matching them to ideal owners are all jealously guarded secrets that were coveted by rival wandmakers.
However, this passage also makes it very clear that he wasn’t the first person to put a magical core in a piece of wood and use it to channel magic, so he didn’t invent the concept of the wand from scratch.
In an old page from her website, JKR explains how several characters have wand woods which match their birth wood from the Celtic calendar:
Some time after I had given Harry his holly-and-phoenix wand I came across a description of how the Celts had assigned trees to different parts of the year and discovered that, entirely by coincidence, I had assigned Harry the ‘correct’ wood for his day of birth. I therefore decided to give Ron and Hermione Celtic wand woods, too.
This may have been unintentional, but Malfoy is the same. The Celts were a dominant culture in the UK prior to the Roman conquests, so perhaps this lends credence to the idea that Ollivander arrived with the Romans, and he picked up this idea from the Celts. Or maybe it really just is coincidence.
But we can go back further. In a Comic Relief interview in 2001, JK Rowling said that "to do really good spells, you need a wand". Pottermore has at least one (alleged) instance of advanced magic that would pre-date the Ollivander shop:
Andros the Invincible. This Ancient Greek is alleged to be the only known wizard to have produced a Patronus the size of a giant.
The civilisation of Ancient Greece was over by the sixth century BC, at least a century before Ollivander opens. Assuming this report is accurate, and that you can't conjure a Patronus wandlessly, then this would be an earlier example of wand usage. (HP Wikia asserts that he mastered wandless spellcasting, but I can't find their source.)
Herpo the Foul is another ancient Greek wizard, responsible for creating the Basilisk, the Horcrux, and lots of other dark magic. We don't have dates for his activity, but this is another suggestion that wand-based or wand-like magic was around at the time of the Greeks.
Since we have Greeks performing relatively advanced wand-based magic, I'd guess the first wands were invented before even them (or at least before Herpo and Andros). There would have been some time between the invention of wands and this advanced magic.
The first explicit mention of wands
Ollivander aside, these examples only allude to the use of a wand, but none of them explicitly mention them. The earliest canon mention of a wand with a date that I can find comes from Quidditch through the Ages:
The famous painting Giinther der Gewalttlitige ist der Gewinner (Gunther the Violent Is the Winner), dated 1105, shows the ancient German game of Stichstock. […] The bladder-guardian was allowed to use his or her wand to repel these attacks.
There are illustrations (e.g. Rowena Ravenclaw on chocolate frog cards in video games) that depict people with wands at earlier dates, but I don't know if you would count those as canon. There are also mentions of spells, duelling and charms which presumably require wands, but it's never said explicitly.
Somewhere in Europe, maybe Greece?
The Pottermore page for Uagadou, the African school of magic, tells us that wands were a European invention.
Most canon instances of wizards and witches from the BC era hail from Ancient Greece. Since Greek philosophy and science was relatively advanced, and formed the basis of a lot of Western culture, perhaps the Greeks were the first to use wands. This could have been absorbed into the Roman Empire, then carried by Ollivander to Britain.
Ancient Egypt strikes me as another plausible candidate: they had curses (as evidenced by the need for Curse-Breakers like Bill Weasley; see Prisoner of Azkaban). But this is a throwaway line, so we can't place their wand usage, or lack thereof.
I don't know enough classical history to make plausible suggestions for other candidates (if there are any).
Based on Ollivander's accounts above, it wasn't his ancestor who started the business. I also doubt it would be any of the named wizards above, as I think inventing wands (or being credited as such) trumps any other magical achievement.
As with most primitive inventions (fire, the wheel), the identity of the creator is probably lost to history. It's also plausible that multiple people invented it independently, and there is no one person responsible.