Palamedes, also spelled Palomedes, Palimedes or a number of other variant spellings, is a knight in Arthurian mythology. He appears in several Arthurian romances, including Le Morte D' Arthur. For the most part, he has the same character development as most Arthurian heroes, which is not much. He jousts and fights, has a rivalry with Tristam for a damsel, and is one of the seekers of the Questing Beast. The most notable feature of Palamedes is that he is a "Saracen", sometimes being described as the son of the King of Babylon. Depending on the legend, he is not Christian for either some or all of his stay at the Roundtable. Palamedes' being ethnically and religiously separate from Celtic, Christian Britain is not taken up as much of an issue in the romances, although there is some suggestion that some of the tasks he sets about to do, like hunting the Questing Beast, is due to his status as an outsider.
Although the Arthurian romances date from much later than the actual historical existence of Arthur (and indeed, ironically were often written by the descendants of the people that Arthur fought against: the Anglo-Saxons), it is possible that Arthur's war companions could have included people of North African or Middle Eastern descent. From a modern viewpoint, especially given the romanticization of Celtic cultures as being natural and closer to the earth, the resistance of Arthur was the last stand of the wild Celts against the encroachment of civilization. But on the other hand, Arthur wasn't only a Celt: he was a Roman. The Romanized Celts weren't fighting against the encroachment of civilization, but rather to protect urbanized Roman civilization against what they would have seen as savage Germanic tribes. For people raised in Roman Britain, Egypt and Mesopotamia would have been part of the civilized world, much more than the seemingly closer lands of Germany and Scandinavia. There was, historically, African and Middle Eastern soldiers who settled in Britain, so the story of Palamedes might have a historical background.
Given the general lack of historical information we have about Arthur's historicity, and about late Roman Britain, it is impossible to tell whether Palamedes is the remnant of a historical figure, or whether he reflects the medieval interest in the exoticized lands outside of Europe, or some combination of both. But the presence of Palamedes, as sketchily described as he is, shows that the medieval attitude towards ethnic and religious diversity was more complicated than might be assumed from a modern perspective.