Medieval Travel Was Unpredictable
When you use the phrase "Medieval" in relation to traveling across the open ocean out of sight of land we are going to have to assume that you are referring to the Later Medieval Period (Approx 1250 to 1500). This is because it really wasn't until around the mid to later 12th century that accurate open water navigation became possible thanks to the introduction of the compass. Prior to this sea navigation was primarily based around staying in sight of shore and keeping an eye out for landmarks. The Exception to this was Viking Longboats that used astrological reckoning. I think it's safe to assume your character isn't on board one of those because unless he was a Viking then he would be a slave, and missing his boat would not really be an option that he had.
In any case, we take something highly for-granted today, and that is regular departure scheduling. We have had it for centuries now, so it is not even within our mind that there was a period when things were NOT highly scheduled and regimented. Ships showed up when they showed up, and they left when they left. There was no regular Friday 4pm one way from Byzantium to Venice. The availability of ships going where you wanted to go was based highly on the volume of traffic between both ports, how much you were willing to pay, how well trade between those two nations was doing, seasonal weather conditions, and random chance.
Additionally, purchasing berthing on a seagoing vessel was not like today. You negotiated with the captain for a berth. There really weren't any dedicated passenger ships, one had to find a cargo ship with a berth available and negotiate with the captain for how much you would pay for a place to sleep and the provisions you would need for the journey. If you were very poor one might even trade labor for berthing, and this always carried the risk that the captain might decide you do really well at swabbing up vomit from the poop deck and decide your employment was rather more of a permanent affair than you had originally planned on. On the flip-side, if you were one of the extremely wealthy or powerful you might just charter the entire vessel to go wherever it is you wanted to go at a departure time of your choosing.
The way "average" people got around was usually by finding whatever was available that would get you closer to wherever you wanted to go and doing it again at the next port. If you ran out of options (or money) you would need to complete the journey overland, or risk press-ganging (getting kidnapped and enslaved by your captain) by trading labor for passage.
Travel within the later medieval period was reliant upon a myriad of factors. Dependent upon any or all of them one might be inconvenienced by a day or two, or could possibly miss the last ship headed out before the stormy season and end up stuck in that port until the next one arrives next year. There were no set travel itineraries and there really was no way one could accurately pinpoint how long between ships traveling along a specific long route one might have to wait. The only thing that can be stated about sea travel in this period is that it was highly unpredictable and expensive. Missing your vessel's departure would be cause for much anxiety. Your Idea that he might have to travel on a ship to another port and try to find a vessel departing for his final destination there is perfectly feasible, though the exact itinerary of the trip is not possible to predict.