Options I found:
All in all, my research seem to always point to taking a plane rather than a ferry... unless you really have a special reason for avoiding planes (transporting loads of luggages, transporting a bike, fear of planes, or else).
Here is another good reason not to take the ferry in Indonesia How safe are the ferries in Indonesia?
Note: you must add circa 12 USD to every flight with AirAsia if you have a checked baggage
Note regarding trains going from Singapore to Johor Bahru: There's no point in taking the train to JB, the new terminal is very inconvenient and services are infrequent and unreliable. Take a bus instead.
Final note: there is nothing "special" to do in Medan, so if you arrive before 4pm try to plan your journey to your final destination straight from Medan (typically using a tourist bus or a public bus), roads can be dangerous at night so many transports do not work when it's dark (after 7pm). The hotel/hostel hosting you can provide more info, it's a typical thing to do.