One of the first toothed birds ever discovered, Hesperornis paddled with its hind feet to hunt fish and evade marine reptiles in warm, Cretaceous seas. UnexpectedDinoLesson via Wikimedia under CC By-SA 4.0
Smithsonian Magazine has an interesting article about birds with teeth. Before the K-Pg event at the end of the Cretaceous Period, most birds had teeth, but those species are rarely discussed. One of the first toothed bird discovered, was Hesperornis in the 1870's.
Early birds such as Archaeopteryx don’t look all that different from the small, carnivorous dinosaurs they evolved from, with long, bony tails; claws; and, of course, teeth. Other features we associate with living birds—egg-laying, feathers, complex systems of air sacs—all evolved among non-avian dinosaurs first, too. And while Mesozoic bird fossils are rarely uncovered, owing to their small size and fragile bones, experts have discovered enough complete skeletons from deposits formed in the ash or fine-grained sediment at the bottoms of ancient lakes to get a feeling for how much the birds varied.
Most Mesozoic birds with teeth, for example, belonged to a group called the enantiornithes. Among their ranks were long-jawed birds with tiny teeth such as Longirostravis, crustacean-crunchers such as Eoalulavis and even potential sap-eaters like Enantiophoenix.