The Roman army was a heterogeneous body, made up of soldiers from across the empire. Although in most places the majority of new recruits would have come from the local populations around bases (at least by the mid-imperial period), that did not stop units or individuals being moved around as needs changed. If an emperor was planning a particularly large new campaign, or if there was a specific emergency in one place, whole legions could be shifted from one region to another. Troops needed for Marcus Aurelius' campaigns in Germany are one of the probable reasons for the abandonment of the Antonine Wall and the re-fortification of Hadrian's Wall. A few decades later, when Septimius Severus was in the province, his death was apparently foretold by a black African soldier serving in Carlisle (HA. Severus 22).

We have evidence for the movements of individual soldiers from their gravestones and other inscriptions. Although there are problems with these, in terms of the conditions of survival and the fact that what remains is not a representative sample, they nevertheless give a glimpse of what was possible. From Britain (because you mentioned it in your question), we have several African soldiers. Two are known from inscribed altars from near Hadrian's Wall, and are interesting examples to think about. Here's the first (RIB 897):

To Jupiter, Best and Greatest, for the welfare of the Emperor Marcus Antonius Gordianus Pius Felix Invictus Augustus and for his wife Sabinia Furia Tranquillina and for their whole Divine House, the Cavalry Regiment, styled Augusta for valour, Gordiana, set this up, when commanded by Aemilius Crispinus, prefect of cavalry, born in the province of Africa from Tusdrus under the charge of Nonius Philippus, emperor’s propraetorian legate, in the consulship of Atticus and Praetextatus.

Here we have a man from Africa commanding a cavalry unit, and working directly under the provincial governor. I suppose this is the higher level of individual you might have been thinking about in your question, but our second is a less distinguished example (RIB 816):

To Jupiter, Best and Greatest, the First Cohort of Spaniards, part-mounted, which is commanded by its prefect, Lucius Antistius Lupus Verianus, son of Lucius, of the Quirine voting-tribe from Sicca in Africa, (set this up).

Verianus raises an important point. Here is a man from Africa commanding a cohort of Spanish troops, demonstrating that we can't always take the ethnic labelling of Roman military units as indicative of the actual origins of the men serving. Nevertheless, some men within these groups are likely to have come from the home region, even if not all of them did. On Hadrian's Wall, alongside the Spaniards in the previous inscription, we also have mentions of Moors (RIB 2042), Tungrians (RIB 3326), Palmyrenes (RIB 1171), Hamians (RIB 2172) and Asturians (RIB 1064). The Vindolanda Tablets, some of the most incredible surviving evidence for daily life in the Roman army, were predominantly written by members of a cohort of Batavians, originally from modern Belgium.

None of this should be too surprising to us really. The Roman empire was incredibly well connected, with very good road networks and (mostly) peaceful seas, making movement easy. Moreover, as I said at the beginning, the army remained a mobile institution even after the frontiers began to settle down. Talent was drawn from across Roman-controlled regions and applied where it was most needed. If there was a need for cavalry on Hadrian's Wall, why settle for substandard local recruits when you can move the best quality horsemen from Spain?

As a final note it's worth pointing out that there was a moment of internet controversy on this exact point a few years ago. The BBC released a video depicting a black man in Roman military uniform, which elicited rage from some quarters. Many prominent Roman historians, including Mary Beard, Matthew Nicholls and Neville Morley explained why this was perfectly reasonable. Their blogs still make useful reading, even if the heat over the video has long since died down.

They would travel quite far actually. During the time of the Republic, the Legions went where they were needed, and you would often end up fighting and garrisoning in regions of the world thousands of miles from home. The Legions that took part in Julius Ceasar's invasion of Britain for example, include not only Italic peoples (from rome and its allies in italy) but also Soldiers from the roman holdings in Carthage and Greece (with Greek, phoenician, and north african ancestry) as well as auxiliaries from both the Gaullic tribes across the channel, and Numidians from north africa (related to modern Berbers).

the Conquest that occurred in 43AD by the Emperor Claudius used a professional army drawn from all around the intermediate. We don't know exactly which legions were involved, but the policy of the time was for Legions (and their attached auxiliaries) to serve as far from the lands they were first raised in as possible, in order to minimize conflicts of interest in loyalty. so when Claudius drew Legions from Gaul and Germania to invade the British isles, the men of those units would likely have been a mix of men from Italy, Iberia (spain), Greece, Syria, Egypt, Numidia (north africa/libya), and generally from all over the Empire. Once Britain was conquered, the Auxiliaries stationed there to garrison it came from places like North Africa, egypt, and what is now the middle east, while Auxilaries and later legions raised in Britain were sent off to fight and garrison in places Like Dacia and Panonia (what are now the balkans) and palestine. In 175 AD at the end of the Marcomannic wars, Emperor Marcus Aurelius even had 5,500 Sarmatian Iazyges Cavalry (a nomadic steppe tribe that had settled in what is today Ukraine) made into auxiliary troops after they were defeated and assigned to Hadrians Wall, which combined with their families would have several dozen thousand people joining the already substantial garrison of the wall. (in fact, it is currently believed by some historians and mythographers that it was the descendants of these Sarmatians, and their Heavy cavalry traditions, that formed part of the basis for the earlier King Arthur tales in later centuries)