That's kind of a tricky one. Depending on how you would define fictional vs. quasi-historical works, this attention to "canonicity" would stretch back at least into antiquity - you might compare with Plato's Republic which says:

Then the first thing will be to establish a censorship of the writers of fiction, and let the censors receive any tale of fiction which is good, and reject the bad; and we will desire mothers and nurses to tell their children the authorised ones only.

This is a form of "canon" taken to the extreme of censorship, but it shows the idea of rendering a judgment on works of fiction and rejecting some while accepting (and enshrining) others is very old.

Then you have works like Virgil's Aeneid (29-19 BCE) extending from Homer's Iliad, and was followed by works like Dante's Divine Comedy (1320) which extended from both - you could described the Aeneid and Divine Comedy as "fanfiction," but it would be more accurate to say that Virgil took Homer's quasi-historical fiction as canon when creating his own epic, and Dante in turn took Homer and Virgil (among others) as canon when writing his; this was an early example of a shared universe of sorts - though the authors were separated by centuries, they built on each other's works.

"Canon" is a tricky concept when applied outside of Biblical studies, because there literally is no definite authority available; for fictional works by a single author, the author themselves is usually seen by fans as the determinator of what is and what is not "canon" - and that usually requires them to have a series of stories or novels or other creative works starring a recurring character (or cast of characters) and/or setting, with some episodes that are clearly "out of character" and chosen to be ignored, or explained away, and to actually make that statement.

I don't think it's quite possible to determine a "first" for that sort of behavior, because it depends a great deal on reader-author or reader-reader interaction - before you have a canon, you have to have a quarrel about what is not canon, so to speak - but I would argue that it probably sprang up with the advent of mass literacy, relatively cheap fiction, and the series novels and stories of the late 19th and early 20th century, as exemplified by early popular series like Edgar Rice Burrough's Tarzan or L. Frank Baum's Oz novels. Both writers were faced with the fact that they hadn't set out to write a single epic work, but had written a work that became popular and then sought to extend it with additional works - which at times involved errors on their part, adding new elements which didn't quite jive with the old, or even crossovers; such as when Burroughs wrote Tarzan at the Earth's Core (1930), which crossed-over his Tarzan and Pellucidar tales, establishing them in the same "universe."

You also have "unauthorized" extensions of a given work - there were innumerable sequels and episodes of this kind of thing in literature, you might compare the various Arthurian romances which had different authors all spinning stories around basically the same set of legendry - an early contemporary example would be Edison's Conquest of Mars (1898) by Garrett P. Serviss, which is a quasi-sequel to H. G. Wells' extremely popular The War of the Worlds (1897). Serviss' work was, like Virgil and Dante's, built on a previous work, though it was an original piece of fiction in its own right; the difference being, Wells was still alive and never "authorized" the sequel - so if you treat the author of the original work as the authority, Serviss' story certainly isn't canonical. As Wells himself never wrote a sequel to War of the Worlds, this is a bit a of moot point, and innumerable sequels, prequels, and variations have been written since then, the "canonicity" of which depends entirely on the reader.

This can be distinguished from a bit of literary "borrowing" - for example, Robert W. Chamber's The King in Yellow (1895) includes references to Carcosa, Hali, and Hastur from Ambrose Bierce's short stories "An Inhabitant of Carcosa" (1886) and "Haïta the Shepherd" (1893); these are somewhat closer to literary in-jokes or allusions than an effort to say that Bierce's stories are considered "canonical" by Chambers.

When you talk about Star Trek and the Cthulhu Mythos in particular, however, you're talking about a "shared universe" - this is a concept where multiple writers are contributing to a setting through interconnected stories or creative works, usually (but not always) at around the same time. It can be fairly argued that what became known as the Cthulhu Mythos, created by H. P. Lovecraft, Robert E. Howard, Clark Ashton Smith, Frank Belknap Long, August Derleth, Robert Bloch, Henry Kuttner, etc. was one of the first - but it was also initially a very loose mythology; a sort of literary game where these writers, most of whom were publishing in Weird Tales and corresponding with one another (or at least with Lovecraft, who was a prolific letter-writer) would create new entities, tomes, and locales, then insert allusions to the others' creations in their own fiction to give the impression of a shared universe. This was all very haphazard, so sometimes the allusions and references weren't correct - but there was really no common authority for these things. So for example, in Lovecraft's The History of the Necronomicon he claims there are no more copies of the Arabic manuscript now in existence - but in Clark Ashton Smith's "The Return of the Sorcerer" (1931), there it is! Likewise, Lovecraft sometimes sought to maintain the continuity of the common mythology to keep it consistent, as when he would write to Robert Bloch in June 1933:

Also—you give Howard’s von Junzt the praenomen of Conrad, whereas at least one printed allusion (which I put in a story I ghost-wrote for a revision-client!) establishes it as Friedrich. Howard himself, amusingly enough, did not give von Junzt a first name so far as I know. (Am I mistaken?)

• Letters to Robert Bloch and Others 56

Of course, while Lovecraft did give von Junzt the first name Friedrich, it was only in his letters - not any published fiction - and Robert E. Howard never specified it, so Bloch can be forgiven for this "mistake" - but you can see how with a number of different writers contributing, all creating more or less independently, this sort of thing can quickly build up and get confusing!

The 1930s science fiction and fantasy fandom is really when you started seeing the develop of "fanon" - where the fans strive to create a canon, working from the original materials. One of the earliest examples of that is about another Robert E. Howard creation: Miller and Clark's A Probable Outline of Conan's Career (1936).