I don't think there is a specific rule for this; it's something you've just got to learn on your own through practice. (Kind of just like how på, til, for aren't explained all that much.)
Might it be than it is more "How the way is called?" if we use på, and more like "What
s the roads name?" if we use af ?
"Street" instead of "road" is considered wrong... Is that really wrong?
Yes. "Vej" means way in many many other contexts. Wonder why not in this one!?