Perhaps it was when he rejected idolatry. Hhaza"l explains (exact source I don't know immediately) the reason Mordekhai was called a Jew, Yahudhi, although he belonged to the tribe of Binyomin, is because all who reject idolatry are called Jews, Yahudhim, (as if there is a broader and a more exact definition for the term). This is based in the fact that the name Yahudho derives from the 4 letter Name of HaShem, י and ה followed by ו and ה, combined with the phrase הודיה (thanks/praise) and/or any of its variants; thus the name means roughly "one who praises/thanks HaShem", as opposed to idols.
As to why all of the people of Israel are referred to as "Jews" can certainly be explained in this way, and also that the tribe of Yahudho was the primary surviving tribe during the Babylonian exile, after many of the northern tribes of Israel were majorly exiled by Assyria beforehand. Albeit, amounts of all tribes do exist within the Jewish people today. And in the future, Moshiahh will be able to say who is who.