Since you've used the KJV, all the quotations and links in this answer also reference the KJV.
We can trace God's dealings with Israel back to Abraham in the famous passage Gen 12:1-3, where it is through Abraham that "all families of the earth be blessed".
After Solomon, just as Rehoboam was ascending the throne, the nation of Israel split into (1) the Northern kingdom, which consisted of the bulk of Solomon's kingdom and kept the name Israel, and (2) the Southern kingdom, which took on the name Judah even though it included people from other tribes. The term "Jews" refers to the people in the Southern kingdom, which survived as a sovereign nation longer than the Norther kingdom. (It can be argued that the term applied to all descendents of Abraham through Isaac who remained faithful to God. My point here is simply to point out the historical roots of the word "Jew".)
When Jesus conducted His earthly ministry, He identified His own ministry as to "the lost sheep of Israel" (Mt 15:22 onwards). When Jesus commissioned the disciples in Acts 1:8, the order specified was "in Jerusalem, and in all Judaea, and in Samaria, and unto the uttermost part of the earth". In each case, it was to the Jew first.
Paul's view of the Jews was a people "to whom pertaineth the adoption, and the glory, and the covenants, and the giving of the law, and the service of God, and the promises" (Rom 9:4).
So given the path through which the gospel came, it was appropriate for Paul to deliver the message "to the Jew first".