The man stepped off the elevator and started down the corridor.
I have seen started used like this before without adding eg. walking after it. Is it perfectly natural use of started?
It is a perfectly natural use of 'started'.
Lexico's definition 1.3 of start is:
[no object, with adverbial of direction] Begin to move or travel.
Their examples include, he started for the door and we started out into the snow.
According to Etymonline, start evolved from the Old English styrtan and its variants, which meant to leap up or to move or spring suddenly. By 1300 this meaning had evolved into flinch or recoil in alarm, which is still one of its meanings today.
The meaning begin to move or travel only appeared in 1821. It bears no suggestion of alarm or suddenness.
The word has a rich etymological history. Originally, it meant "move briskly, move swiftly, spring suddenly, recoil in alarm" and I think it still preserves this meaning. I don't come across it very often but this ngram chart says it's quite common.
I don't think it's simply interchangeable with "walking" because there must be an element of suddenness, rush, alertness. He didn't just nonchalantly walked down the passage, he rather hurried/flew/ran through the corridor.