A book, Salamis of Cyprus: History and Archaeology from the Earliest Times to Late ... offers an estimation of the population of the city-kingdom of Salamis during your desired time frame. The estimate is derived by applying percentages of the population against the number of troops recorded as being fielded.
This model used applies a figure of 21% of the population which could be enlisted in a war, so comes up with the following (emphasis mine) :
Considering that the number of almost all men (80-85%) of the kingdom
aged 20-49 at the beginning of the war was 18,000, then the entire
male population of that age group would have amounted to 21,000 to
22,500 men. Mogens Hansen, whose model ('Model West 4' of A.J. Coale
and P. Demeney) I used in this research, ascribes this age group to
around 42% of the entire male population, or 21% of the whole
population. Applying this percentage to the total, the whole
population of the kingdom at the beginning of the 4th century BC can
be suggested to range between 101,000 and 107,000, including men women
and children.
So Salamis, arguably the largest of the city-kingdoms at 400BCE, had an estimated population of around 104,000.
--- Extrapolations:
From this you can extrapolate an (unlikely-think upper limit) maximum population of around 1 million, or you can do some more math and apply some Rank–size distribution or Zipfs power laws to try to tighten up the estimate.
An article which explains Zipfs law as applied to groups of city populations can be found here.
Running the numbers through Zipf based on Salamis as the largest of the city-kingdoms at 104,000 I come up with a lower-end estimate of around 304,000 for the entire island population.