You are welcome,
Put "sama" will change the politeness level. But I think we dont have to add sama here. Sometimes better to add "sama" and sometimes not, depend on context.
I think the correct one would be kaze no nusubito. Kazeno already includes the second no you wrote. As you may know you can join words in japanese some times, so kazeno would be like "of the wind".