After watching the relevant sections of the films, the videos from Enter the Matrix, and researching on the Internet I can't find any explicit indication how Smith first gained access to the backdoors -- we simply see him access the hallway. I can think of three possible explanations for how he first gained access.
1. The Agents have access to the backdoors as part of their jobs.
As a former Agent, Smith may have always had access to the backdoors. The Agents are security programs so it may make sense to give them backdoor access. The fact that Agents can already move throughout the Matrix by possessing bluepills means the Agents would not typically need the backdoors, but the backdoors would provide them a way to move around the Matrix quickly without possessing bluepills unnecessarily (and be forced to erase the bluepills' memories of their possession). Also, access to the backdoors could help them hunt down exiles which have access to the backdoors.
If this is the case then Morpheus was unwittingly prophetic while training Neo on the nature of the Agents in The Matrix:
We've survived by hiding from them, by running from them. But they are the gatekeepers. They are guarding all the doors, they are holding all the keys.
Morpheus was speaking metaphorically and did not know about the backdoors yet, but if this is the case then the Agents really are guarding all the doors and holding (almost) all the keys.
2. Smith acquired access with the help of the Merovingian.
The Merovingian was holding the Keymaker prisoner at the time Smith became an exile (following his destruction by Neo in The Matrix), and exiles require the help of the Trainman (who works for the Merovingian and controls the link between the Matrix and the Machine City) to re-enter the Matrix. Smith undoubtedly encountered the Merovingian, and the Merovingian would be willing to help Smith since the Merovingian and Smith have a common enemy: the Oracle. The Merovingian therefore gave Smith the key(s) to the backdoors. The fact that the Merovingian and his minions can access the backdoor hallway is proven by another clip from Enter the Matrix, where Cain and Abel steal the key for The One from the Keymaker (clip starts at 29:40 in this video).
3. Smith assimilated a program that had access to the backdoors.
An example of such a program is Seraph, although Smith did not did not gain access by assimilating Seraph since Smith already had access to the backdoors before assimilating Seraph (proven by the Enter the Matrix clip in the question -- Seraph opens a backdoor for Niobe, and then she encounters Smith in the hallway). We never see such a program but presumably Seraph is not the only program with keys that access the backdoors.