Restarting a app from scratch
Since you said it's not listed under Manage Storage or in iCloud or GameCenter, here are some other things to look for or try

An in-app account unrelated to your apple accounts. Some apps use this for things like saving your progress cross platform e.g. progress on ios device shows on android device. If it has one you'll want to log out and create a new account. Also check social media sign-ins as this could affect it as well.

A reset progress button in the app settings, you may have to hunt through menus but many apps have something to completely reset all information/progress within the app. 

Signing out of iCloud and GameCenter before reinstalling the app will help diagnose if that is the problem, and most apps will ask which save file to use on the next start up.