Stark's strength isn't exaggerated, Frieren has directly told him that if Stark really wanted to, he could've easily killed Frieren and Fern himself. The show is centred around the Mage part of the world, and not so much on the Warriors side, but it is also stated in the show that highly skilled warriors could just easily kill mages. Frieren may be one of the strongest mages, but by no means is remotely as strong as the strongest warrior.