In Bastok Mines, you go all the way west, you will see the map marked with Zeruhn Mines. Once inside go all the way west, as the path lets you. The NPC there will let you pass through the gate. Continue with the west direction and you will eventually zone into Korroloka Tunnel. And even more west is the only non teleport access to the Altepa Desert region.