It's hard to say.
First, proper nouns have to be capitalized, but it's not that easy with things and animals, you can find various names of things commonly written in lower case, like streets, so you should see this street exact official name, that could be lower case since the beginning even when the "logic" tells you that all nouns should be capital letter.
Second, when a certain street have a large amount of certain commerces or offices, is very common that the street ended being referred as "calle de los/as..." and the name of the office, commerce, etc. Even when the street have a totally different "official" name. I don't think that "commonly spoken" name should be capitalize, all the words should be lower case, not only "calle".
For example, in my city there is a street commonly called "calle de los institutos" just because there are two colleges and an university building in that street(sometimes you can even hear things like "en los institutos" or "por los institutos").
Again, in that case I think both words should be lower case, because it's not the noun of the street, it's just a spoken reference.
The user fernando.reyes tells us that the street exists and is called "Calle de los Notarios", so in this case it should be capitalized.