First, a general comment: one must always remember that there are two major categories of ‘native’ Japanese words, namely the true native vocabulary inherited from the prehistoric Japanese language, and the nativised vocabulary imported from Chinese. Although there are some words whose classification is unclear (うめ（梅）、うま（馬） etc.), by and large it is obvious from the ‘sound’ which class a word falls into. 出来る is of the first category. The strongest evidence for this is that the reading is not what we would expect from an imported Chinese word spelled with those kanji: indeed, the word しゅったい is much closer to the expected reading しゅつらい.
I admit this isn't conclusive: it could well be a calque (i.e. a direct translation) from Chinese, or even a direct borrowing of some Chinese word (but not 出来) which was turned into a native verb. But I personally believe the latter is unlikely, and I am not in a position to say one way or another about the former. A solid answer would require knowledge of both languages and their histories.
However, after a little search, it seems that the theory that できる was really originally a compound of 出る and 来る does have some evidence. According to Daijisen, it's from the カ変 verb でく, and Daijirin says でく is a contraction of いでく, which is consistent with the theory that it's a compound of 出る (classical: いづ) and 来る (classical: く). Moreover, Daijirin gives the following definition for いでく:
Sense (5) is precisely the ‘potentiality’ we're interested in, and sense (1) is exactly what you would expect from the kanji: ‘to leave and come here’.
But, I'm still a little suspicious: the example Daijirin gives for sense (5) comes from a 15th century text, whereas the example for sense (1) comes from the Man'yōshū—a 7th/8th century text. And Daijisen doesn't even give ‘potentiality’ as a possible meaning in its definition of いでく.
As for your additional question: The word でき is clearly obtained from the stem of できる, and the meaning is more or less what you would expect from such a derivation.