As far as I know linguists consider language arbitrary. If so, how does etymology work? We have a word and we trace it back to its origins. Then, we find that it either comes from a different language or originated at a certain time. But then what? We have no idea how the word originated originally or why it came to mean what it does. So do we have any idea how or why any word came to mean what it does, originally? And if not, because language is arbitrary, then words got their meanings by someone just deciding a certain sound would represent a certain meaning and people went along with it?
Language is arbitrary as you say but it is also not created by authority. There's no one person or committee saying: "Let's start a new language, and we'll call all those four legged things we ride 'horse'" (except for the wildly out of the ordinary constructed languages like Esperanto).
There are all sorts of theories about the true, way-back-when, something-out-of-nothing origins of words and syntax, but they're all very speculative and quasi-scientific (no one is there to record the early language speakers). Looking at the behavior of other communicating animals (dolphins/whales, birds) gives ideas, but tends to the "Gosh we think it could have been like this, maybe."
A grunt here, a sigh there, eventually people, out of arbitrary association with other activities, modified and distinguished these sounds, not through any dedicated process or choice, created words associated with meaning. Well, that's a theory with little support other than plausible analogy.
I think I might understand what you are trying to ask in your question. Basically, you want to know whether there is a point where etymologists have to stop because you can't go further. (?)
Remember that when linguists try to reconstruct forms (proto-Germanic, proto-IE etc.), they say nothing why a cow is "a cow". In most cases, the connection between form and meaning is purely arbitrary. Historical linguists study how words (and other linguistic units) change and why. They don't explain why those words have a particular form.
cf. Jespersen's remark that "the earliest accessible stage remains unexplained and must be taken as it is" (Jespersen, 1924/1992, The philosophy of grammar, p. 81).
We know exactly how the first words arise, at least in the case of signed languages. Gestural communication is systematized to create homesign, which then may be reorganized and grammaticalized to create conventional language. The process is described in detail in:
First words can be defined both ontogenetically and phylogenetically, correspondingly, this is the research topic of both language acquisition and language evolution. (the division of labor of the same research topic does not mean the two fields are not closely tied!)
There are several good books to start with:
The books above both, more or less, deal with the arbitrariness of sign. Also there are some relevant papers:
The Origins of Arbitrariness in Language. Michael Gasser. Proceedings of the Annual Conference of the Cognitive Science Society (2004) Volume: 26, Publisher: LAWRENCE ERLBAUM ASSOC PUBL, 10 INDUSTRIAL AVE, MAHWAH, NJ 07430 USA, Pages: 4–7
The arbitrariness of the sign: Learning advantages from the structure of the vocabulary. Monaghan, Padraic; Christiansen, Morten H.; Fitneva, Stanka A. Journal of Experimental Psychology: General, Vol 140(3), Aug 2011, 325-347. doi: 10.1037/a0022924
It's quite possible we'll never know. Words don't leave fossils, and writing is a very new occurrence in the great scheme of things.
If I recall correctly, the absolute limit assumed for finding shared etymological origin is around 10,000 years. Of course, that number is arbitrary, but it gives you a ball-park idea of how far back we can expect to reliably recognize traces of similarity.