Here, try this:-
Kid is like...4. Yeah, 4.
Kid meets legendary baby.
Kid meets momma, who is abviously p***ed at some human going near her child.
Momma nearly kills kid.
Kid left traumatised.
Work from there for the fear an getting Lugia kid in plot.
And cute and cuddly? I find spiders that, yet people still have arachnophobia.
Fear is typically overcome by pure strength of will. They usually must WANT their fear to stop, or find it's a stupid fear after a large number of situations which help them realize this.
Watch the eight movie. The kid in it is afraid of Pokemon, and two 'cute and cuddly' Plusle and Minun take a good portion of the movie to help him overcome it, and they showed him Pokemon aren't that bad.
And seriously, Legendaries. In game, meh. In story, ffs Ho-oh can come back from the dead, Lugia can create storms just by leaving the ocean, Mew originated all Pokemon, Rayquaza is over 3 million years old, Suicune can purify water, Celebi can travel through time...
Need I say more? THE LEGENDARIES ARE POWERFUL. In Lugia's case, it's a FORCE OF NATURE. You don't have a ten year old mess with nature.
My 2p.