The main point is the difference between political and economical border. While political border didn't imply the economical border, there were usually no serious crossings in old times. On the other hand, any economical borders inside the political bodies immediately created the crossings with guards, checking and so on. At the first moment when a crossing became profitable, it appeared.
Inner and border customs are well known for feudal Europe.
Control in ports could start in Phoenicia, Mesopotamia or Egypt. The old dynasty economic was not a state one, it was based on the private activity and propriety. (according to Herodotus). We don't know for sure, if there was some state control for these traders other than on the market itself. But I would suppose that there was such control - the state simply had to have the possibility at least to be the first customer.
Entrance into a town could be such crossing even before that - Jericho existed 10t. years ago, and while it had a wall (archeologically proved), the entrance had to be controlled (or the wall becomes senseless). I think Jericho gates is really the older crossing that can be known now, for it is the oldest known organized human society.
As for personal control on borders, in Russia it existed and was well developed in the 16 cent. They were introduced by Ivan the Terrible for quarantine against plague epidemia in Western Europe. I have read about quarantine in 10th cent. in Byzanc, too.
As for political control, the most known old border were the walls on the borders of Roman Empire. Adrian one (122 AD) seems to be the oldest of them. I am afraid, nobody knows now how the border control looked like these times.
As for passports, AFAIK, they were introduced first in Russia by Michael I, according to ideas of an early socialist Charles Fourier. These are inner passports.
As for visas, the first, obviously, were visas for going out. For in-visas require existence of the stable system of official representation in almost all neighbour states.