Being as Conan Exiles takes place between Xuthal of the Dusk (Slithering Shadow) and A Witch Shall be Born. We have a good idea of a region where physical access to the Exiled Lands can be found:
Somewhere between Xuthal and Khauran as indicated by the circle in the image. From that information and from what Conan says himself, he kinda just wandered in. That’s pretty consistent with how he shows up pretty much everywhere.