English, Portuguese, Dutch, and Russian all have velarized [ɫ] at the syllable coda. When did this start happening in English?
It's not very easy to be certain about things like this, but there are some Old English vowel changes that suggest that [ɫ] was an allophone of /l/ in at least some environments during the Old English period.
Wikipedia talks about it:
/l r/ apparently had velarized allophones [ɫ] and [rˠ], or similar, when followed by another consonant. This is suggested by the vowel shifts of breaking and retraction before /l r/, which could be cases of assimilation to a following velar consonant.
- *lirnian > liornian > leornian [ˈleorˠnian] ('learn')
- *erþe > eorþe [ˈeorˠðe]
- *fællan > feallan [ˈfæɑɫɫɑn] ('fall')
Of course, the distribution of [ɫ] and [l] is variable in modern English depending on the accent, and this probably was true in the past as well.
I don't know of any evidence about the presence or absence of velarization in older forms of Germanic ancestral to English.