If you consider the time involved (over 800 years), it's quite plausible. But it's also quite likely that you and I also are descended from the same King.
Consider, you have two parents, two grandparents, four great grandparents, eight, sixteen, thirty two. For each generation you go back, the number of ancestors doubles.
So you got back 10 generations, you have 1024 ancestors.
Go back 20, you have about 1,000,000
Go back 30, you hav about 1,000,000,000 which is more people than there were in the world at that time. Obviously if you back far enough your ancestors are cousins of one form or another.
How far back is 30 generations? Well, a conservative estimate for a generation is 20 years, so 5 generations is 100 years. 30 generations is 600 years. And we are talking over 800 years, so 40+ generations. It's quite likely that anyone with english roots could (if records were perfect) trace them back to pretty much anyone who has any living descendants.
Zerjal et al. (2003) identified a Y-chromosomal lineage present in about 8% of the men in a large region of Asia (about 0.5% of the world total). The paper suggests that the pattern of variation within the lineage is consistent with a hypothesis that it originated in Mongolia about 1,000 years ago, and thus several generations prior to the birth of Genghis. Such a spread would be too rapid to have occurred by genetic drift, and must therefore be the result of selection. The authors propose that the lineage is carried by likely male-line descendants of Genghis Khan and his close male relatives, and that it has spread through social selection due to the power that Genghis Khan and his direct descendants held and a society which allowed one man to have many children through having multiple wives and widespread rape in conquered cities.