I don't think there is any example of the exact thing you seem to be asking for: a "common phoneme" that has an identifiable "first appearance" in Modern English. There are some relatively uncommon phonemes that do not occur in native vocabulary, but that do occur in words that entered English around the Middle English period.
The consonant /ʒ/
The sound /ʒ/, as in the word “vision”, is commonly described as a phoneme that was introduced to English through foreign influence, even though the most common English words with /ʒ/ actually didn’t come directly from words that had /ʒ/ in a foreign language. Rather, /ʒ/ most often shows up as a result of coalescence of earlier /zj/. But /zj/ didn't occur as far as I know in native English words, so /ʒ/ only shows up in words from French and Latin (at least partially: glazier is built on the native stem glass, but has a French suffix -ier).
There are also word with /ʒ/ where it came directly from French /ʒ/, as in mirage, prestige or genre, but the sound is a bit more marginal and unstable in word-initial or word-final position: for example, some people replace /ʒ/ with /dʒ/ in "genre". (Actually, even in word-medial position, /ʒ/ is a rather "marginal" sound in that it has low contrast with /ʃ/ and there are a number of words that show variation between the voiced and voiceless sound in different accents or idolects: e.g. Asia, version, fission. But the "marginal" status of the contrasts between /ʒ/ and /dʒ/ and /ʒ/ and /ʃ/ isn't something that we only see with non-native sounds: it's well known that the contrast between /θ/ and /ð/ in English has a similarly low "functional load".)
I don't know what the "first" English word with /zj/ or /ʒ/ was.
The "choice" diphthong /ɔɪ/
Like /ʒ/, the diphthong /ɔɪ/ (as in the word "choice") is an infrequent sound that characteristically shows up in non-native vocabulary (mostly words from French).
Some common consonant clusters do not occur in native English vocabulary, and many common sounds don't occur (or barely occur) in certain contexts in native English vocabulary
If we relax the requirement that the examples be "phonemes", we can look at consonant clusters like /sk/, which doesn't occur word-initially in vocabulary inherited from Old English because of a sound change that turned it into /ʃ/. (I'm not sure if there are any exceptions. I specified "word-initially" because in word-final contexts, there are words like "ask" where I think the /sk/ > /ʃ/ change did not apply in Old English because of the existence of metathetic variation between /ks/ and /sk/.)
Word-initial /v/ or /p/ typically indicates that a word is non-Germanic, although there are a few exceptions like vat (which developed from a dialectal variant pronunciation with voicing of word-initial /f/) and path (whose Proto-Germanic etymon has an unclear etymology).