Zionism isn't precisely the idea of founding a Jewish state; it's more Jewish nationalism (classically, Zionism is completely secular). And it arose as a reaction to increasingly secular and assimilated Jews who found that the newly self-identifying nations were less willing to consider Jew to be German, Polish, Russian, or whatever than the Jews themselves were willing to. This means, practically, that Zionism can't really rise until after nationalism starts to form, because before nationalism and widespread Jewish assimilation (without conversion) and a resulting backlash, there's no reason for it to form.
The question then becomes one of:
-How early can we get nationalism as an idea divorced from religion (or at least only partly connected to it)?
-How quickly after the advent of nationalism can we get Jews trying to assimilate and being rejected?
If what you want is a Jewish state, we might see an early colonizer trying to stick all their Jews in the New World, I guess.
Note well: it's very unlikely for there to be a religious movement to found a Jewish state, especially not in Israel. That would require a Messiah figure, and the Jewish mainstream tended to be very suspicious of such figures. Plus, it would require a strong enough movement to conquer a region that was for around 2000 years either a pat of or next to a large, powerful empire. Granted, often a backwater, but still part of an empire.