Von der MS Hotline habe ich in 2 Telefonaten 2 Empfehlungen erhalten, die mich nicht weitergebracht haben: System Wiederherstellen (habe ich nicht gemacht, weil ich das für übertrieben und wenig zielführend hielt) und Drucker mit Kabel anschließen (was nur gezeigt hat, dass der Drucker dann druckt).
Interessanterweise konnte der Drucker weiter Scans an den Laptop schicken (hat ihn also erkannt), hat aber keine Druckbefehle erhalten.
Beim 3. Anruf kam dann der richtige Hinweis: Druckertreiber komplett de-installieren (nicht nur aktualisieren) und neu installieren, damit er mit Windows 8.1 kompatibel ist. Neustart und seitdem funktioniert der Drucker wieder einwandfrei.
Den Kauf des PC Health Advisor hätte ich mir sparen können.