Wootz steel was already being produced by that time and a sword of it might have made its way to Britain before the fall of the Western Roman Empire. If this were so, could it have influenced the Excalibur legend somehow?
It's certainly possible. I don't remember correctly but IIRC Excalibur wasn't described as made of black steel, whereas Wootz swords very commonly had black blades with water patterns on them. (Sort of like Valyrian Steel in ASOIAF)
Then again the description could have been changed by chroniclers to deify the sword in a way.
Named swords weren't unusualö in the stories of the time, so just about any high-quality weapon might have done. Most likely, the sword ended up with a king because it was unusually good, but it became Excalibur because it ended up with a king.
Ex Caliburn means something to the effect of 'to cut steel', and given that late Rome overlapped with early Dimashq steel it proved curious. Kind of like the old Roman name for Colchester or the Viking sword of Dimashq steel found a while ago.