Yup, that works fine. The plant deer blinks at the resulting ice and then crocuses poke up out of the frozen ground.

Detect magic. Wait, lost magical girls retain their spellcasting as well? Modern thaumaturgy says everything about this situation should be impossible; a creature without a soul can't do magic or even be magic because magic more or less is souls doing stuff. Even unintelligent magical beasts have them to some extent, just... less.*

Maybe local wisdom is wrong about them being soulless? What he wouldn't give for Aliztavagr's soul-sight right now. 

*Faeos operates on somewhat different metaphysics than Golarion.

"Thank you," he tells the doe who probably can't understand him.

Swarms aren't really a threat to him, even asleep, but if he gets woken up again he's gonna go find a cloud.

Flop. 

The doe makes a pretty chiming noise and lies down next to him again. No more swarms appear for the rest of his sleep.

Then he will enjoy a blissful eighteen more hours of rest, and awake from slumber refreshed and recharged. Is the doe still present? 

Nope, she wandered off at some point.

Then he'll move on to his next priority, finding a...

...well, okay, he'll go fishing first, he's a bit peckish. 

He's not conserving spells anymore! That means fishing is extremely easy. His swimming is mediocre at best but freedom of movement renders this irrelevant. He flies out beyond the shallows and plummets into the waves at full speed. The water simply fails to impede his flying in any way. (Also, he can see pretty well in the dark, especially at short distances). It's so much fun. 

People observe and comment on his fishing; if he overhears anybody on a boat or the shore doing so they're all she-ing him.

Eh, it's a reasonable assumption given everything else they know. Honestly as possible receptions go, assuming he's a friendly magical fae thingy is pretty good. Still no harpoons! 

When he's had his fill of sea life, he'll overfly the port in search of either a Rebecca (if she happens to be around) or a church (which he knows by vague description tend to have crosses on top). 

Rebecca is perched in the crows' nest of a new ship.

Tongues. He glides down to hover nearby. "Hello again, Rebecca!" 

"Hi Ipaxalon! Did you sleep all right?"

"Thoroughly. I woke only twice, once when a magical creature happened by and once when a swarm appeared."

"Ooh, what kind of creature?"

He describes the petal-winged doe and her behavior. "I didn't realize they also retained their magic. It's a very unusual phenomenon by my own world's standards. As far as they're concerned, souls are magic, more or less." 

"Well, they're still pretty, just not humans really any longer."

"Indeed. The pattern seems consistent, it's just a very different pattern than I'm used to."

"They live forever, supposedly. Sometimes you hear about a magical girl who's getting really old and decides to turn into something instead of dying the normal way."

"A final gift to the world, or simply a way to leave something of oneself behind...Yes, I could see it being an attractive option. If, ah, you'll excuse the turn of phrase."

Giggle.

"Now that we've reached a population center, I expect I'll want to stay for a time — talking to priests and governors, learning the language, figuring out how best I can help. Yet I feel it'd be a shame to lose touch when one of us can teleport and both can fly. I see you've found a new vessel to grace with your presence; whither are you bound?" 

"The Netherlands, it's not so far."

"Would you like to explore options for staying in contact?" 

"You could see if they'll hire you too? I'm going with them because I bet I can get a ship to South Africa from the Netherlands and they'll pay extra for the chance to have ice around the equator. I don't really have an address for letters."

"I think I'd enjoy voyaging with you again, but I don't think I want to sign on for another long trip without at least an assurance of somewhere to sleep. For now, I was thinking some combination of you leaving a letter at your port of call, and my requesting the captain's permission to study the vessel closely enough to let me find it with a teleport. And if you do settle somewhere in South Africa, it wouldn't be hard to visit, if you'd like that.

"For that matter, teleport takes passengers. I'd need to actually visit South Africa the long way first to be safe, but if your ultimate goal is to end up there, you could bypass the whole 'sailing' business entirely were you so inclined, whether by magic or initial flight. Thoughts?"