It was used since the aegaen Peleset took over following (probably) some kind of brokered peace with Egypt, yep. The peleset seem to have been pretty quickly Canaanized by their new subjects, but that polity ceased to exist like 500+ before Jesus and the Roman province of the same name wasn't founded until 100+ years after he died.

So it's probably not appropriate to call that area Palestine during this period.

And regardless of that, the term has very specific and vivid modern connotations that needlessly muddy the waters when we're talking about a time when rabbinic Judaism was less than maybe 200 years old and Islam still like 600+ years in the future.