rationalskepticism.org

The taxa of extant birds have this overall phylogeny:

• Palaeognathae
• Neognathae
  
  • Galloanserae
  • Neoaves

• Palaeognathae - unambiguous fossils only in the Cenozoic, possible Cretaceous fossils
• Galloanserae - Vegavis lived just before the K-Pg boundary
• Neoaves - around the K-Pg boundary, like these recent finds

Palaeognathae and Galloanserae all have flying members, so their K-Pg ancestors were likely also flying. Otherwise, re-evolution of flight several times.