As a rule of thumb I generally make a texture 2X the size its going to be on the screen, eg if in the final render its going to be approximately 500 X 500 Pixels I would go for a 1K map on that object.
You could get a way with less such as 1.5X or 1 X but going lower that can cause you problems with texture distortion.
"No pressure, no diamonds" Thomas Carlyle