ok, ich glaube ich habs herausgefunden (aber wie ich da jetzt drauf gekommen bin dürft ihr nicht fragen...):
Wenn ich kein Menü definiert habe dann nimmt wp_nav_menu als fallback wp_page_menu.
Dafür gibts auch eine Walker-Klasse - und zwar Walker-page (und nicht Walker-nav_menu).
Diese muss ich einfach erweitern.
Was ich nicht wusste war, dass die ganzen erweiterten Klassen im Prinzip den eigentlichen Code der Ursprungsklassen auch noch einmal komplett enthalten und nur an ganz wenigen Stellen angepasst sind - da stand ich irgendwie auf dem Schlauch.
Also - so scheints jetzt zu funktionieren...
Trotzdem Danke für die bisherigen Hinweise mit dem Filter - das kann ich sicher auch nochmal irgendwo brauchen! :-)
Vielen Dank und viele Grüße
derpunkt