How old can fairies become?
As of now, there's no official answer, but at least older than 4200 years.

Summarizing from the Wikia about Fairy Clan:


  Longevity: The average lifespan of a Fairy is between 1000 to 1500 years. They do not appear to physically age and they never suffer from illness.


Now, comparing the known fairies' age:


Invisible: ?
Cisca: ?
Dahlia: ? (former, 2nd king/queen)
Melik: ?
Elaine: ±1000
Ende: 1000+
Puora: 1000+
Helbram: ±1300 (deceased)
King: 1300+ (current king)
Gloxinia: ±1400 (former, 1st king)
Gerheade: ±4200


Although most of them are mentioned in between 1000-1500 range, Gerheade is an exception, and she's not even a king.

Thus, assuming there's nothing that prevents their natural aging (e.g. Elaine, Helbram), and since they don't suffer any illness, fairy king should even be possible to live more than 5000 years.