[Nerwen]

Cuivienen
It's not clear exactly where the Sea of Helcar lay, but it was it was in the far north-east of Middle-earth, effectively off the map as far as the rest of the story is concerned. (Tolkien did draw a map showing it lying right next to the Blue Mountains, but I think this was an early conception- it certainly won't fit the action of the published Silmarillion, anyway.) Cuivienen ceased to exist at some point, but it's not specified when or how.

The Great Journey from Cuivienen
No, this wasn't just across Beleriand, but right over the "known" lands (Rhovanion, Eriador, etc.), plus, presumably, some others that are, again, outside the borders of the maps. It is supposed to have taken two hundred years or more. Not all Elves took it, and of those that did, many dropped out before reaching Beleriand, and were therefore the first people to settle those areas.

The Helcaraxe
This lay somewhere to the north of Beleriand. No relation to the Sea of Helcar.

The Two Trees
These could not be seen from Middle-earth, which at that time was lit only by starlight.