It does seem totally random across the board to trigger Velanna's quest. With her approval at 17, for me, when I triggered it I don't think I'd given her any gifts. I'll go back and check that. I'd guess it can trigger anywhere on the road? Or maybe it's tied to the road between Wending Woods and other places? Can you actually trigger it without Velanna being in the party? I'd think we'd see more mention / posts of a fight with a Dalish clan along the road in that case. Just trying to think of possible answers, I don't know why it's so random / varied.

I'll be hitting Wending Woods later, will take notes!
In Origins, my first playthrough, it took me 3 days of playing and and an hour here, an hour there of traveling back and forth on the road from Redcliffe to finally trigger the star metal cutscene for Starfang. Second playthrough, I got it straight out from camp on the way to Redcliffe.