Nothing happens at all.
This is essentially a question of two parts. Part one is unstated, but important, and it is the question of who is legitimate monarch.
First of all, legitimacy does not, as Tony Robinson claims, rest on blood. Legitimacy rests on being accepted as legitimate. This sounds like a tautology, and on some level it is, but on another level it is not. The rightful monarch is the one that is accepted as rightful monarch, and this is often stated in some act of law. In many cases that law is a list of rules on who is "the rightful" heir, but who is it take makes up that list? Right, whoever is currently in power. There is no "God given" correct succession. No-one has a right to be a King or Queen that exists outside the peoples acceptance of him/her as monarch.
The legitimate succession is therefore the one that is accepted as being legitimate.
In England, the rules of succession has been changed several times, most lately in 2013, mainly to make succession gender-neutral. England even was a commonwealth between 1649 and 1660, and there was no monarch at all. Now, British law is complicated, so exactly what laws are relevant and still valid is beyond me (apparently the Treason Act of 1351 is still valid, just as an example, and had to be modified when changing the succession in 2013), but Wikipedia claims that the relevant laws all say that the succession are legitimate descendants of Sophia of Hannover. So whether Edward IV was legitimate or not is irrelevant.
Saying that the Windsors are illegitimate is therefore incorrect. Had Edward IV not been accepted as legitimate somebody else would have been monarch today. This is the ore truth in the TV program. But it does not make Queen Elizabeth illegitimate. The current British law says that the legitimate monarch is Elizabeth Alexandra Mary of Windsor, and she also is the one that is accepted as the monarch.
But what would happen if theoretically it is shown that the current monarch is not the lawful monarch?
Most likely, what would happen is that a law would be passed, making the monarch the lawful monarch. It is of course quite possible that the current monarch somehow is implied by the scandal himself/herself and is forced to abdicate. Say that it turns out that Queen Elizabeth is not the legitimate child of George VI, and that she has been active in keeping this a secret. Who then becomes monarch? Well, whoever has the support. Although in this hypothetical case the nearest legal heir to the throne really is Prince Richard, Duke of Gloucester, it is also quite possible that Prince Charles instead gets to be monarch. He might not be the legally correct one, but he is born and bred to be monarch, and giving him the title would be easiest, as otherwise pretty much the whole royal house needs to be changed. He also seems quite popular. This will likely also require an act of law, but since Prince Richard is unlikely to have a large amount of followers in the parliament sitting and waiting to make him King, it's a law that would be easily passed.
Or perhaps it would be the final nail in the coffin for the monarchy and Britain might be made into a commonwealth again.
So onto part 2 and the stated questions:
How would this affect a kingdom (i.e. UK) today?
Either a new law would be passed that makes the current monarch (or a descendant) the lawful monarch, or whoever is next in the line would become monarch, or the monarchy will be abolished.
Would the new head of state need to re-affirm age-old decisions and, if so, how far back would they have to go?
No. A monarch stepping down does not invalidate any laws or decisions made under that monarch.
Has this situation ever arisen in the past, how big was the gap (I'm tempted to call it the "Royal Hamming Distance"), and how was it dealt with?
Not that I'm aware of. In the past, if this situation would have arisen, at it possibly did with Edward IV, it would simply be hushed up and ignored. Today with democracy and mass media this would be much harder to achieve, but should it be discovered somehow that somewhere in the line between Sophia of Hannover and Elizabeth II there is an illegitimate child, nothing would be done about it. The monarchs since then were all accepted as legitimate, and therefore they are legitimate.
(As a side note, Richard III was able to get Edwards IV's marriage to Elizabeth Woodville declared invalid after Edwards IV's death, which meant that Richard III became the new king, instead of Edwards IV's son Edward. Of course this just happened because Richard III had the practical power and support in the parliament at that day, and he also had Edwards IV's young sons killed. So if Tony Robinson want to find the actual "real king" of England he should look amongst Catherine of York's descendants, but I think that line might have died out, making for a boring TV program. But it's an example of what might happen if you decide that someone is not legitimate.)