There are some very old streets in England, the oldest believed to be Vicar's Close in Somerset, from around the 14th century - but that is actually quite modern compared to others.
Pompeii is an obvious example from the 6th-7th century, where the street names were clearly signed. A street plan shows that pretty much all streets and alleys were named.
Ancient streets have been found in Jerusalem, which are thought to have existed from about the 4th-6th century. These have been mapped, which is been used to excavate them at the moment. I don't think it would be that much of a leap to suggest that if the streets had been planned in any way that they would also have been named - if not when they were first created, at least by the time they were mapped. The article that I linked to doesn't mention street names explicitly though, but if places like Pompeii were naming smaller streets, then it would be likely that they were in Jerusalem from at least the 6th century too.
Now, this is where my 'official internet sources' run out. I can't seem to find anything earlier than that. But one observation is that it's human nature to want to name locations and points of interest. If there was not an 'official name', it's likely that the locals would have had a name for certain streets and places anyway. You have already mentioned the reasons why people would do that, but as an example: I live in a village which was bombed during WWII and at the back of the houses on a field is a massive ditch where a bomb fell. The area is just common land and has no name, but local people call that area and the path that runs behind the houses 'The Bomb Hole'. Everyone in the village knows what you mean when you say 'I'm walking down the bomb hole' - you are taking a shortcut down the path next to the common.
So, to directly answer the question - what I can see from sites that exist today, the 6th century seems to be the earliest period where smaller streets were officially named. But saying that, it's likely that smaller streets were named earlier than that, but the maps of the time don't show it - this may say more about the style of the maps than prove that smaller streets were not named (maps of the period seem to show the areas of a city and the major roads, rather than what we would call a street map today).
This is my first answer, so any suggestions welcome. Also, if i'm totally off with this answer then let me know and i'll delete it. Many thanks.