Was the Privacy Policy linked on the Play Store listing description as well?
IIRC, there was a recent change in the last 12 months or so to require a link to the privacy policy on the listing.
You should be able to file an appeal and get it reinstated using this form:
https://support.google.com/googleplay/android-developer/answ...