How to get to The Barren Coast
In order to get to Barren Coast you first need to head over to Toxxulia Forest - the Erudite starting zone. You can reach this zone easily through Plane of Knowledge; the stone to Toxxulia Forest is found in the evil side of the zone.
Once you're in Toxxulia, Barren Coast's zone line is in the south eastern portion of this zone, shown on my map above. What you're looking for is a cave like entrance shown in my screen shot below. Run into that cave and you'll zone into Barren Coast.