> Gibt es die feste Regel, dass Landesstraßen immer "secondary" sind und Kreisstraßen "tertiary"? Oder spielen funktionale Aspekte, die von der tatsächlichen Klassifizierung abweichen, auch eine Rolle?

Das ist etwas umstritten, aber viele Mapper halten eine Klassifizierung nach funktionalen Aspekten für sinnvoll.
Siehe dazu z.B. das Wiki (https://wiki.openstreetmap.org/wiki/Attribuierung_von_Stra%C3%9Fen_in_Deutschland#Innerorts) oder verschiedene Diskussionen im Forum (https://forum.openstreetmap.org/viewtopic.php?id=75539; https://forum.openstreetmap.org/viewtopic.php?id=69473).

> Warum ist die Wittenberger Straße als "tertiary" getaggt?

User puma515 hat vor einiger Zeit großflächig Straßen strikt nach dem Schema Kreisstraße=tertiary umgetaggt.
Für die Wittenberger Straße ist das der Änderungssatz 121072548 (https://www.openstreetmap.org/changeset/121072548).

> Weil es eine Kreisstraße ist? Funktional und von der Verkehrsbelastung her ist sie doch aber eher "secondary".

In Elmshorn kenne ich mich nicht so aus, deshalb kann ich zu dieser konkreten Straße leider nichts sagen.
An dem Änderungssatz habe ich mal einen Kommentar hinterlassen und auf diesen Hinweis verwiesen.