What's the difference in meaning between "evidence" and "proof"?

In the simplest terms, proof is conclusive but evidence isn't. Evidence is more of a suggestion.

In your example sentence, the use of evidence is to make it clear that there are other possibilities, such as maybe the dating being wrong, or the evidence not being human in origin.

Some fine answers already, but to add a simple explanation:

Evidence may be used to form a theory or hypothesis.

Additional evidence may refine such a theory.

Proof shows the theory to be a fact.

Example: Adding one apple to a basket with another apple results in a basket with two apples in. This could be proof that 1+1 is indeed equal to 2, but only evidence that 2+2 may equal 4. We might say that adding another two apples (hopefully resulting in 4 apples in our basket) has shown proof of our theory, or that the theory has been proven.

In your example the author is saying that the evidence (e.g. maybe carbon dated pottery or the like) has led to the theory that humans existed in Saudi Arabia for at least the last 20,000 years. But just like any other theory, the conclusion built upon the understanding of this evidence may be incorrect, and even the understanding, or dating may be incorrect.

Evidence means:-

A thing or things helpful in forming a conclusion or judgment: The broken window was evidence that a burglary had taken place. Scientists weigh the evidence for and against a hypothesis. [American Heritage Dictionary via the Free Dictionary].

Proof means:-

The evidence or argument that compels the mind to accept an assertion as true. [American Heritage Dictionary via the Free Dictionary]

In some fields of enquiry (Law, or the Sciences) a preponderance of evidence, and a lack of evidence to the contrary, would be regarded as a proof of some statement or assertion. In others (Mathematics or Logic), no amount of evidence is a proof. Only a proof:-

a. The validation of a proposition by application of specified rules, as of induction or deduction, to assumptions, axioms, and sequentially derived conclusions.

b. A statement or argument used in such a validation.

would suffice.

In probabilistic terms, evidence increases the probability that a proposition holds, relative to its value without such evidence, whereas proof raises the probability to certainty.

If Y is evidence for X, then

P(X|Y) > P(X)

If it's proof of X, then

P(X|Y) = 1

(Strictly speaking, a probability of 1 isn't quite the same as certainty, but that kind of mathematical pedantry is out of scope for EL&U...)

In order to make a case, you need evidence and an argument. Evidence without argument is just a pile of uninterpreted facts. Argument without evidence is just assertion.

When you have a case, the next question is how convincing that case is. Is the argument a good one? Is the evidence open to other interpretations? Whether the case is proof or not depends on the standard of proof you are looking for. In UK civil court cases, a case is considered proof if it is true "on balance of probabilities", that is, if the court is persuaded that the claim is more likely true than not true. In criminal cases, a case is not considered proof unless it is "beyond reasonable doubt" -- the evidence and arguments are so good that no reasonable person would doubt it. And in mathematics, even that level of proof isn't good enough: something has to be shown to be true beyond possibility of contradiction (ok, I'm blurring the distinction between "evidence" and "axioms" on that last one).

What all this comes down to is that "proof" is a sliding scale, but that wherever you are on it, evidence alone is only one part of a proof.