How did the Apostolic Church manage to integrate different Tribes and Clans under its ambit?

We read in Matt 15:24 , of the initial response of Jesus to the pleadings of the Canaanite woman > He answered, “I was sent only to the lost sheep of the house of Israel.” (NB: Some editions omit the word `house') Collectively, the descendants of the 12 tribes of Israel are known as the house of Israel and are called Israelites. Obviously, all Israelites (descendants of Jacob) are Hebrews (descendants of Abraham), but not all Hebrews are Israelites. Additional family names are used for some groups in the house of Israel. The descendants of Judah (the fourth-born son of Jacob), for example, are known as Jews, and the descendants of Ephraim (a son of Joseph) are called Ephraimites. Now , we see St Paul writing in Romans 1:16: > For I am not ashamed of the gospel, because it is the power of God that brings salvation to everyone who believes: first to the Jew, then to the Gentile. The basic meaning of the word Gentile is “foreign,” “other,” or “non.” Thus, to a Hebrew, a Gentile is a non-Hebrew; to an Israelite, a Gentile is a non-Israelite; and to a Jew, a Gentile is a non-Jew. There appears to have been some confusion in the Early Church as to who the Chosen People were. But for the induction of Gentiles to the Group, there was chance that the Early Church stood terribly divided. My question therefore is: How did the Apostolic Church manage to integrate different Tribes and Clans under its ambit.