Here is the map that is so fascinating to me. Image that you are drawing this map with respect to magnetic north. All of that white area at the top is open water above Siberia and Canada. There is a whole load of Canada's northern coast, as well as Russia's. That area has been virtually ice locked since Magellan, but apparently not while Polo was sailing. Below is a polar projection map - I wish I could have found a better one for comparison here. Clearly, the map above does not show the full extent of Polo's explorations in the north (or the south, either). In fact, he would not have "seen the pole star in the south" unless he got nearly to Greenland's coast.
Recall that his voyages were a mere hundred years or so after the warmest two centuries of the last 2000yrs - it is likely to have been as much as 3F warmer in 1000AD in the north pole area as it is even now. A fairly ice-free Arctic Ocean should not be surprising.
