We appealed and it did not work.
We then complied with their request and added to the privacy policy they we have access to the contacts and we might process them, and yet Google still rejected our app.
In the end we just decided to completely remove every code from the app that would allow us to read the contacts on the phone.
This has now made our app UX worse for the 60% of users who used this feature.
Also, mind that we of course offered the option to never grant this permission so nobody was ever forced to give access to their address book.