Re-reading your question, I realize I made an error. I assumed you meant “Deutsch” as a cultural identity. Geographically speaking, areas beyond Germany are not identified as “Deutsch”, because as Constanze correctly pointed out, it’s not a geographic term.
RAE says that “calle” comes from Latin “callis”, I’m assuming callis is also the root for kalea.
But the biggest source of the confusion is the word order, people from the-rest-of-Spain are used to the last word in the street sign being the name. And in the case of avenida/etorbidea, there is no similarity.