According to the Wallenda family, they earned their nickname here in Akron in the 1930s. From their website:
The Great Wallendas were headliners with Ringling Brothers, Barnum & Bailey Circus during much of the 1930s and 1940s. Once in Akron, Ohio, the wire slipped slightly as they were performing. All four members fell to the wire, yet they were relatively unhurt. The next day, a reporter who witnessed the accident stated in the newspaper, "The Wallendas fell so gracefully that it seemed as if they were flying,", and the headline read "THE FLYING WALLENDAS." That name is still synonymous with the family to this day.
You can see several other sources mentioning this incident, but I haven't actually found a single smoking gun - primary source. They were definitely using the name by 1937, but I can't find it anytime before that.
The Beacon Journal does not have a good online archive going back that far, but I have emailed the special collections desk to see if they can dig out more.
There's also a cool article from the Beacon Journal describing when one of the Wallendas walked over the Rubber Bowl in 1973.
Necco Wafers at the Frozen North and Why Archivists are Awesome