Vanlig problem. Mac bruker Bonjour for å finne printere. Bonjour bruker mDNS. Mange norske ISPer leverer trådløst skrot som ikke støtter mDNS skikkelig (ZyXel, Jensen, visse Altibox; gjetter på ZyXel utifra symptomene). Noen kan fikses med ny firmware, andre ikke.
Sjekk om skrivern har Wireless Direct - slår du på det lager den et eget WLAN som du kan koble Macen til. Funker det da, skaff en bedre router (eller bruk USB).

Dette er min erfaring som tidligere HP-supporttekniker.