(Everything below is speaking of English; other languages have different filler words and I don't know anything about their history.)

Before I get into this I need to distinguish between two types of filler words, filled pauses and discourse markers.

Filled pauses are, by the decree of linguists, "short utterances in spontaneous speech", the two most popular being "uh" and "um". These tend to represent pauses for collecting thoughts. Discourse markers include "like", "I mean", and "you know"; they tend to serve as transitions between sections. Quite often "uh" and "um" are "invisible" in a sense whereas discourse markers tend to be more noticeable and can signal wanting something in particular from a conversation; for example, "you know" being a check with someone listening that they do, in fact, know, and that they should give some sort of negative signal if the conversation is off track. (By a recent study, discourse markers also tend to be more common amongst women and younger people; in other words, even within a country, filler words may different by age or gender.)

The first place we'd like to turn for historical filler words is literature; unfortunately, while we have some very old uses of filler words, we don't have them being attempted in any "authentic" way. It wasn't really until the 19th century that authors tried to go full naturalist with filler words as "interruptions", but to lay down very old examples first, here's "hem" in 1526 from John Skelton:

Hem, syr yet beware of Had I wyste!

"Hum" appears in Shakespeare (Merry Wives of Windsor).

Hum: ha? Is this a vision?

Jumping to the 19th century, Charles Dickens uses both words in the filler sense, in Little Dorrit:

I have a -- hum -- a spirit, sir, that will not endure it.

and elsewhere in the same work:

Gardens are -- hem -- are not accessible to me.

Rather more elaborately, here's an 1853 clip from Robert Surtees's novel Mr. Sponge's Sporting Tour:

'Ha--he--hum,' says Lord Scamperdale.

'Meet at the Court,' mumbled his lordship--'meet at the court--ha--he--ha--hum--no; got no foxes.'

Now, the problem for those hopeful at discovering old, new filler words: "haw" when given verbally was just "uh", and "hum" was just "um"; the spelling simply differed.

"He" is perhaps the more interesting of those and seems to have been an "eh". "Eh" shows up that way elsewhere; here's a clip from 1876:

"To you? oh, ah, eh -- twice their value, my good Fraulein Elsa."

and one from 1885:

Eh, eh, eh, Freule? And how is it with the town councillor, and with his daughter, and with you all, eh, eh, eh? Fine seasonable weather; not to warm, though, eh, eh? And what is the latest news in the town, eh?

By the end of the 19th century, the "eh" sound seems to be mostly relegated to the function above: forming transitions in the same manner as a discourse marker, as opposed to a filled pause. "Eh" is alive and well in parts of eastern Canada, but more as a discourse marker (or indicating a question).

...

So, if "eh" used to be an actual filled pause, as opposed to a discourse marker, ​wouldn't it be nice if we could hear it that way?

While we have a recording all the way back in 1860, "unfortunately" it is reciting lines from the play Aminta so it doesn't include filler words. (Also, it's in Italian, and I've been sticking with English.) However!--

One of the oldest recordings we have on phonograph is from Thomas Edison himself, on a recording discovered at the Edison National Historic Site in 1995; inside, was a paper:

Thomas A. Edison talking from N.Y. to Buffalo Buffalo to Chicago Etc. Etc. Made in 1888

Here is the recording. You may notice right off the start the word "uh" -- this is the currect record for earliest "filler word" we have recorded.

Uh, now, Mr. Blaine, as you’ve been nearly around the world, I’ll take you around the world on the phonograph. I’ll not charge you anything.

So, perhaps it is not surprising -- nor exciting for this particular question -- that Edison uses the word "uh". But check out the next part of the recording (and note the Youtube transcriber misses this word, but it is clear once you hear it!)

I’ll take you on a steamer, eh, a Cunard steamer to Liverpool, and from Liverpool to London, from London on the London & Brighton Railroad to Brighton, and from Brighton we’ll go on those little two-cent steamers across the English Channel to Calais.

Technically, you can think of the "eh" still feels a bit like a section transition, but it definitely occurs in the middle of a sentence rather than at the end. Admittedly, this isn't as exciting as you might hope for? ... we essentially have "eh" transition from a more general filled pause to a discourse marker. But perhaps, given the history of English over the centuries, it's just as interesting when we find something that's stable as opposed to something that changes.

...

Erard, M. (2008). Um...: Slips, stumbles, and verbal blunders, and what they mean. Anchor.

Gemma, M., Glorieux, F., & Ganascia, J. G. (2017). Operationalizing the colloquial style: Repetition in 19th-century American fiction. Digital Scholarship in the Humanities, 32(2), 312-335.

Laserna, C. M., Seih, Y. T., & Pennebaker, J. W. (2014). Um... who like says you know: Filler word use as a function of age, gender, and personality. Journal of Language and Social Psychology, 33(3), 328-338.