After Elessar's death, Legolas and Gimli also took a ship and went into the West.
Strictly speaking, Legolas shouldn't have been allowed either, as Tolkien says
But the promise made to the Eldar (the High Elves – not to other varieties, they had long before made their irrevocable choice, preferring Middle-earth to paradise) for their sufferings in the struggle with the prime Dark Lord had still to be fulfilled: that they should always be able to leave Middle-earth, if they wished, and pass over Sea to the True West, by the Straight Road, and so come to Eressëa – but so pass out of time and history, never to return. ... [Letters, #154] (emphasis mine)
Legolas (and his father Thranduil and presumably some others who led a population of Teleri and possibly even Avari) were Sindar, and while considered Eldar, they were not Calaquendi, i.e. High Elves, as per the Sundering of the Elves chart in the Silmarillion.
Was Legolas given special dispense, just like Gimli and the Ringbearers?
Wouldn't that mean he said farewell to his entire people and his father (we never hear about his mother in Tolkien's male-dominated universe) forever? Beyond the end of the world, as I believe it's described in the parting of Elrond and Arwen? With those left behind to become
rustic folk of dell and cave [Galadriel in LOTR]