Teniendo en cuenta que los elfos solían procrear en tiempos de paz, sería bastante lógico pensar que Legolas hubiera nacido en esas fechas que dice Beregond, como así lo hicieron Elhadan, Elrohir y Arwen.
Sin embargo hay que tener en cuenta que, por ejemplo, Elrond estuvo toda la SE sin esposa (menuda sequía :P). Fue en los comienzos de la TE cuando se desposó con Celebrian para, tan solo en 21 años, tener a sus hijos gemelos.

En nuestro caso, por los Apéndices se sabe que Thranduil viajó al Bosque Verde tras la Gran Batalla del final de la PE. En los Cuentos Inconclusos dice que marchó bajo el mando de su padre Oropher, que se convirtió en rey del Bosque Verde. Tras morir en la Dagorlad su hijo se convirtió en rey. Thranduil pudo haberse casado durante la SE, o incluso antes de partir al Bosque Verde al final de la PE. Así que Legolas pudo haber nacido incluso 3000 años antes de la TE.

Lo que quiero decir es que es imposible determinar su edad, aunque hacer apuestas personales es bastante divertido :P. Un saludo.