Hey there,
you have to talk to an NPC looking at the ocean on the right side of Sashila Village (accessible by surfing).
He informs the guard that you're allowed entry into Sandstream Cave.
As for the interaction with Damien in front of the afromentioned cave you have to kick the Ex-Xen Grunts out of "their" building, if you chose that path he should bust into the help center shortly after you entered to inform you about shady activity.
I hope this helps.
Looks to me like someone does something wrong
Y' know what, since it doesn't seem to work for whatever reason, could you upload your savefile here?
I intend to give you a Xatu over that way
Hey there,
you could recieve a Natu if you interact with the Totem Pole in Rhodocrine Jungle on a clear day without a Ill-Fated Doll.
But be that as it may, I could give you one Xatu, if you still need one