There was no technological impediment to building horse-drawn railways during the medieval period. The problem was financial. The capital cost of horses, wagons, fixed wooden rails etc, and there was no economic incentive to build one when, as
@Undeadmuffin points out, carts were more flexible for multiple roads and canals were more efficient for long-haul travel.
The idea of using tracks instead of flat roads was ancient, being used at least as far back as the Greeks, in quarries and moving ships by land. The first animal-drawn wooden railways (that I know of) emerged through coal-mining, and were first used underground within the mines. They gradually started being used on the surface to move high volumes of coal from mines to towns, or to river transport. These were certainly in use by the early 17th century, and possibly earlier.
But note the context: high value good, being transported with high-frequency, and without a convenient alternative, i.e. can't use water transport. This is the sort of situation which makes the investment worthwhile. It needs a high level of usage to justify the capital cost, and no way of building a canal or otherwise using water transport.
So to have something like this emerge earlier, you'd need an economic situation which justifies it. It would need to be primarily cargo, with any fare-paying passengers being only a bonus, not the core purpose.