I'd like to add some more detail onto Zhen Lin's answer. My source is primarily Shogakukan's 1988 version of their Kokugo Dai Jiten Dictionary, Shinsou-ban (Revised edition).
Morphology and Phonology
Modern 出{で}来{き}る comes from older 出{で}来{く}る, comes from older 出{で}来{く}, comes from older 出{い}で来{く}. The oldest form is clearly a compound of 出{い}づ + 来{く}.
出{い}づ idzu (usually reconstructed as idu for Old Japanese) was the original form of modern 出{で}る deru. This belonged to a class of verbs that conjugated a certain way, called a 下{しも}二段{にだん}活用{かつよう}動詞{どうし}, literally lower two-step conjugation verb.
- The lower part referred to the vowel that the stem ended in. Upper verbs ended in -i, and lower verbs ended in -e.
- The two-step portion is more officially translated as bigrade in many English-language references. This means that the stem vowel only has two forms. For a lower verb, those vowels are -u and -e.
So when idu is conjugated into the 連体形{れんたいけい} or "attributive form", it becomes ideru -- stem of ide- + attributive ending -ru. The ide- part is what we see in the historical development of 出{で}来{き}る. Over time, the low-pitched initial i- sound was lost (vaguely similar to how unstressed syllables sometimes fall out in English), producing modern stem form de-.
来{く} ku was the original form of modern 来{く}る kuru. Much as happened with nidan verbs, the attributive form replaced the previous 終止形{しゅうしけい} or "terminal form", adding that extra る that disappears in other conjugated forms. This same kind of development happened in verbs like 食{た}べる and 起{お}きる, which similarly have disappearing final る.
Semantics
The original meaning was just what we would expect from this compound: 出{い}づ "go out" + 来{く} "come" == "to come out". This was used literally, as well as figuratively in the senses of "to appear, to become manifest".
The figurative sense then extended to express the general sense "to come into existence anew", with more specific senses of "to occur, to happen, to be born; to be created, to be made, to be set up; to be produced, to come to fruition", and then "to be completed, to be finished (generally with positive overtones)".
This idea of latent existence was further extended to mean one has the ability to make or do something.
In slang contexts, it was even used to mean "to have sex", perhaps similar to the development of the English phrases "to get it on, to get some".
Timing
As to when the various senses developed, I have less information than I'd like. The earliest citation in Shogakukan for the "able" sense is a quote from the 鹿{しか}の巻筆{まきふで} published in 1686. The earliest citation for the "appear" sense is from around the mid-1400s. However, these are all using the dekiru form.
Looking at the older dekuru form, Shogakukan provides a quote from around the 1420s, using the "appear, happen" sense.
For the oldest ideku form, we get quotes from the Man'yōshū, all the way from the very beginning of Japanese literature in any form, dating from roughly the 300s through 700s. At the earliest stages of the term, the meaning was apparently limited to "come out; appear". The "newly arise, happen, occur" senses are cited to quotes from the early 900s (Tales of Ise) and early 1000s (Tale of Genji).
Digging through what I have here, it looks like the "able" sense is relatively recent, appearing only from the early Edo period. The extension of meanings over time, though, seems to be reasonably clear, and is consistently native to Japanese -- 出来る did not derive from Chinese.
Conclusion
If this Japanese verb really did not come from the Chinese, how do the kanji characters for "to go out" and "to come" end up giving the nuance of potentiality in Japanese?
I hope the above answers this. Please comment with questions if things aren't clear, and I can edit as needed.
Can anyone find out authoritative sources on the actual etymology of 出来る?
Shogakukan is reasonably authoritative, similar in ways to the reputation of the Oxford English Dictionary as a resource for English.
Also, is the origin of 出来る somehow related to 出来{しゅったい} (meaning: occurrence) or 出来{でき} (meaning: workmanship, execution etc)?
出来{しゅったい} originated as a phonetic shift from the expected on'yomi of しゅつらい. Both しゅったい and しゅつらい, as on'yomi, are borrowings from Chinese. (Note that not all on'yomi terms are borrowings from Chinese, but most are.) Both terms express meanings of "appear, occur", and "creation, completion" similar to native-Japanese できる.
The meanings for 出来{でき} derived in a similar fashion to the native Japanese verb. Dekiru == "to appear" > "to be created, to be finished", and from this, noun deki == "creation, finish" > "workmanship".