The term "Jew" is an Anglicization of "Judean" which comes from the Greek Ἰουδαῖος (Ioudaios). Technically, it can simply be a regional distinction, that is someone who is from Judea. But it can of course represent one's ethnicity. Greek who happened to grow up in Judea would not have identified himself as a Judean.
In the book of Esther, the Hebrew "Yĕhuwdiy" (יְהוּדִי) is translated Jew, but in this case the Hebrew is etymologically connected to Judah (Judahite, or Jehudite). Though not all the Israelites in Esther are Judahite, this term is used to encompass all of them, showing that it has become, even at the time of Esther's writing, a universal term.
In the Israelite's return from Babylonian exile in around 500 BC, only the tribes of Judah, Benjamin and Levi (who had been in the southern kingdom of Judah when taken captive by Babylon) returned as representative tribes. While remnants of other tribes did exist, only these three return in large numbers and with intact genealogies.
The name Judah, as before in the kingdom of Judah, continued to dominate. In Greek it became Judea, and thus we have Judeans.
So while it can be technically taken as "Judahite", the term "Jew" was expanded to refer to all of the Israelites of Judea.
Therefore, Paul is a Jew, of the Tribe of Benjamin. Both statements are correct and consistent.