The simple answer is to determine which is the stronger of the two cultures, and bastardise the names from the weaker into the stronger. The theory here is that people from the weaker culture will feel the need to assimilate into the stronger to survive, which will probably require them to change their names to fit in with the acceptable concepts of naming convention. How do you Anglicise the Hungarian name Istvan? Steven (Stephen).
Sharing the same language doesn't mean they share the same culture. Language and culture are completely different things. Language is a communication tool, culture is an expression of communal identity.
Naming conventions themselves are pretty fascinating. There's generally 3 known conventions, of which one is now pretty much universally used in modern societies. It's important to understand that a naming convention is how we determine someone's name. There is a second layer to them which I will explain in a bit.
- Lineage/line of descent (most common now)
- Physical appearance or countenance
Amerindians (perhaps this is a stereotype) traditionally use the 3rd option. They are given names that have no bearing on who their parents are or which community they come from.
The Occupational convention was prevalent in early medieval England, which gave us surnames such as Thatcher, Cooper, Shearer, Baker, Miller etc.
The lineage convention (most prevalent), has been around as long as any others. It consists of adding an extra name to a person's given name to define their heritage. A simple example of this is by taking your father's surname as your own surname.
The Second Layer
Once the convention has been chosen, we would need to know how to apply it. Let's work with lineage here because it has the most variables.
First define lineage.
- Patrilineal: focus on the father
- Matrilineal: focus on the mother
- Ambilineal: focus on either parent or both
Second choose syntactic method.
- Direct Adoption: take parent's name and use it without adaptation
- Gender Classifier: take parent's name and prepend/append gender classifier
Standard Anglo-cultures use the direct adoption method. I take my father's surname, as he took his father's surname etc. Just to note; traditionally, Anglo-culture is patrilineal, which is why we take our father's surname. In modern times there is the accepted practice of ambilineal naming, wherein we apply a double-barrel surname (mother's & father's combined with a hyphen).
Traditional Norse, Hebrew & Arabic cultures make use of the gender classification method. Here are some examples:
Norse: father's given name + -son, -dottir appended. (Still used in Iceland I believe) Karl Magnusson.
Hebrew: father's given name + ben prepended. Simon ben Gabriel
Arabic: father;s given name + ibn prepended. Ahmed ibn Mohammed
So to round up, even though your two cultures speak the same language, their naming conventions could be completely (or partially) different. It would make sense to try to apply the naming convention of Culture B to the people of Culture A if they are interacting in Culture B and are from the weaker culture.
Here's some examples for you:
Norse -> Arabic:
Karl Magnusson -> Karl ibn Magnus
Arabic -> Nore:
Hafiz ibn Rashid -> Hafiz Rashidson (sounds a bit weird, but that's what bastardising is all about)
Arabic -> Anglo:
Hafiz ibn Rashid -> Hafiz Rashid (most likely just drop the ibn)
Hebrew -> Arabic:
Simon ben Gabriel -> Simon ibn Gabriel (note both cultures are semitic, so the similarity is not surprising)
EDIT: since you mention the word believable, I'll add this. Believable isn't always about people thinking it's realistic. Get your characters to alight on the weird bastardisation of names from one culture to the other even though they speak the same language. This provides audience with the needed level of believability because their subconscious concerns are shown to have been considered by the author as well.
And on the reason why lineage is the most common now, it's possibly to do with number of social interactions. More people you meet, the higher the probability of meeting someone else with the same name. Therefore the lineage concept comes to mind as a quantifier. This is Bob & that is Bob, but this is Bob son of Greg and that is Bob son of Dave.