OP's highly rated app was more than likely listed higher than the official app rated 2.8 stars hence user reports and its subsequent removal.
Trademark infringement is never a good idea, those other apps could get pulled for the same reason at any time.
It would have been kind & reasonable if Google had given me an opportunity to rectify the issue by re-branding which I would have done in a heartbeat.
Also, I don't understand why their feedback is so cryptic, if it's was a trademark issue why didn't they just say that.
So you cannot just give it any name, it has to reflect the app's functionality? That is weird. I have a project that is named X, but from that alone you cannot tell what it does exactly. It is impossible to give it a name that would do that.
the stated reason was: > your on-device title does not reflect your app’s functionality.
There are several other apps with Eurovision in the name. If the infringement were the reason they are selective with enforcement.