I had literally the exact same issue. They said I had to get them paperwork from Apple's legal department, ignoring Apple trademark page saying it's okay to use the Mac trademark to sell a Mac app which I forwarded to them with an explanation.

My exact ad said "Try _____, a better way to _____ for Windows and Mac".

They didn't mention the Windows trademark. Pfft.