"They told me I was infringing 4 years later... "

Laches is only a defense if facebook knows and it took 4 years. Even then, caselaw suggests 4 years is the minimum you'd ever get to complain about.

"Google reviewed it and approved it 4 years ago."

Not sure of the relevance to the first sentence. It's not the same folks.

"I was never told what to do or how to change it so that my users would still recognize it. Also changing its name in "Cleaner - For Facebook" was suggested (and accepted) for the Safari extension by the Safari Gallery Team. If I don't know what I'm doing wrong, I can't fix it. "

I'm honestly not sure what you expect here. Google doesn't know what's going to make the other guy stop complaining, and if the other guys complains, they have liability.

I expect this is why they directed you to contact the complainant. Google really can't say or do anything here without risking legal liability, unless the other guy basically says "yeah, we don't care anymore". So they aren't. You can't expect Google to offer you legal advice on how to fix this, that's just silly.

Note that contrary to whatever you think - you have recourse here, even if facebook ignores you (i assume you called the complaining place on the phone instead of just emailing folks)

You could go get a declaratory judgement that your app is not trademark infringing. If you did this, and google ignored that, i think you'd have a reasonable argument here.