While I can understand questioning us if he suspects we're spies, this sentence feels very anachronistic to me. As far as I understand it, the modern concept of border security didn't really apply in the middle ages. Passports date mostly from the 15th to 16th century. Even when they were invented, it took several centuries before they became established usage in Europe. Identity documents were not really a thing either. Even nobles from a distant land would probably rely only on heraldry and wax seals, which would be difficult to validate outside their country. You basically could only tell if someone was who he was if you grew up alongside him in the same village. Anyone else you met outside their own town, you pretty much had to rely on what they said to you.
For the most part, in the middle ages, the closest thing to border security would be paying your toll for crossing a bridge or river toll. As far as I know, entering an area outside of a poll station wasn't illegal per se, which is why so much effort was made to place tolling stations in strategic areas that can't be easily avoided (e.g. bridges). Even then, those tolls charged were mostly for the purpose of maintaining the bridge and port infrastructure and were a source of income, not really an identity control exercise. The greatest stop to the one kind of travel which was discouraged (runaway serfs) was in fact their inability to pay tolls to travel overland a great distance. Any travelers who had the ability to pay was welcome to travel - in fact many nobles spent their life constantly moving about, and nobody bothered them much. So did merchants.
Most places probably wouldn't keep any sort of records over who paid their tolls at a gate, although some exceptions may exist, they would be few and rare. Because you didn't want to have to pay a scribe to run the tollkeeping, basically. It was simpler to collect the money and send it to the lord. I find it quite doubtful any guard captain has the resources to question all ships on the island as to whether we came on that ship. Even if he has the ability to do so (all ships on the island are grounded?), I very much doubt there is such a thing as a law preventing a small, private ship from coming ashore on a beach in most places of the world at that place in time. You're thinking about westphalian borders... which weren't a thing until Westphalia, basically. There were more worries over highway bandits and the costs of tolls than whether you had the right to visit the next town. I find it hard to believe Sicily spent so much effort to maintain airtight borders when it waited until the 19th century to have a proper census. Without that, you can't even tell whether someone living in your town was born on the island without gathering witnesses from the town they claim to be born in. If they moved in after their birth... you took them at their word or you didn't. There is no such thing as legitimate traveling or illegitimate traveling in the Middle Ages. You either could pay, or you couldn't. You either could find free hospitality (pilgrimages), or you couldn't. But either way, unless you were a leper, or believed to spread the plague, no one would stop you if you could pay the tolls.