Shelter can be found inside a cabin, in a trench, down some holes, and in a handful of other places in the desert. The tall pillars do not count for shelter.
You need to walk around in the sheltered spots to lower your exhaustion. You can't just stand still. Walk around for several seconds and (if you have UI effects on) you should see Grove start to recover. The game will also make a sound effect as you recover.
Move from shelter to shelter. If you are starting to get exhausted and haven't found shelter, go back the way you came and try again in a different direction.
Finally, your destination is in the north-east (top-right). Look for some stairs going down.