Well a month later and I have the answer: reinstall the free version and then delete it again. It will ask if you want to remove it from Game Center. Before I think I failed to remove it from Game Center after uninstalling, thinking my stats from the free version would be maintained in the paid one.
Seems like one should be able to delete apps from the Game Center if they are not installed without going through this procedure, but whatever.