When did the last of the High Elves leave Middle Earth ?

[Pitchwife]

All I could find doing a quick search is this from the end of the Prologue to LotR:

There [=in Rivendell, P.], though Elrond had departed, his sons long remained, together with some of the High-Elven folk. It is said that Celeborn went to dwell there after the departure of Galadriel; but there is no record of the day when at last he sought the Grey Havens, and with him went the last living memory of the Elder Days in Middle-earth[emphasis mine, P.]

As Círdan was presumably older than Celeborn (possibly a first generation Elf from Cuiviénen?), this seems to imply that he sailed either with Celeborn or before him.
As for the remaining Elves from Mirkwood and Ithilien (or Lórien, for that matter), I don't think all of them ever left Middle-earth - many (most?) probably remained, slowly fading over the millennia. For all we know, they're still around.

(x-ed with Inzil: Thanks for the Silmarillion quote, I vaguely remembered there was something like this.)

[Inziladun]

I had forgotten that quote from the Prologue. I recalled Celeborn going to Rivendell, but I don't believe Celeborn was of the High Elves. Wasn't he one of the Sindar from Doriath?

The quote from the Silm has another line, which I omitted.

In that time the last of the Noldor set sail from the Havens and left Middle-earth for ever. And latest of all the Keepers of the Three Rings rode to the Sea, and Master Elrond took there the ship that Círdan had made ready.

The only explanation for the apparent variance between the statements in the Silm and FOTR would seem to be that some of the remaining High Elves were not of the Noldor, though I don't know how that could be.

[Pitchwife]

Originally Posted by Inziladun

I don't believe Celeborn was of the High Elves. Wasn't he one of the Sindar from Doriath?

That depends on which of the variant backstories in UT you choose to believe. According to one of them, he was a Teler from Alqualonde; if so, he certainly qualifies as a High-Elf, having lived in Aman - probably the only non-Noldorin High-Elf left in Middle-earth. (Myself, I prefer the Doriath backstory - if only because it gets rid of his Telerin name, one of the most embarrassing unintentional puns in recorded history;!)
Good point about Sam, Lindale. I think we can safely assume that Sam didn't build and/or sail his ship by himself, so some of Círdan's people must have stayed there at least that long. They needn't have been High-Elves, however - more likely they were Sindar from the Falas who came there with their lord Círdan after the ruin of Beleriand. The Noldor never were great shipwrights or mariners, apart from a few illustrious exceptions like Voronwe and his shipmates.
As for the question whether Elladan and Elrohir ever sailed west, see here.

[Tuor in Gondolin]

But Legolas and Gimli came to Valinor much later. Did Legolas
have to return to Middle-earth when Gimli died?

And if Legolas could build a ship capable of making the voyage,
why not other elves?

[Pitchwife]

Originally Posted by Tuor in Gondolin

Did Legolas
have to return to Middle-earth when Gimli died?

No, why would he? The Valar originally invited/summoned all Elves to Aman, and I haven't read anywhere that those who didn't make it the first time were excluded later.

And if Legolas could build a ship capable of making the voyage,
why not other elves?

Maybe they could, but would they want to? Legolas himself had no yearning for the sea before he came to Pelargir with Aragorn & co.