Did Marco Polo travel with Christopher Columbus? Hmmm, my chain of thoughts:
Marco Polo died in 1324. Christopher Columbus was born in 1451. Final answer: no.