If two integers are chosen at random out of the set {2, 5, 7, 8}, what

You're definitely on the right track if you want to prove exactly when it's possible to do this, but when you take examples, unless I've misunderstood what you're saying, I think you're assuming the numbers in the product are equal to a and b. But if you look, say, at this product:

10*4 = (7 + 3)(7 - 3)

then the values of a and b are 7 and 3, respectively, and not 10 and 4. That's why the conclusion you've written, "the two multiplied numbers must be either both even or both odd" is technically not right, as your example of 5*8 demonstrates (there we have one odd and one even, but we can still write the product as a difference of squares). Your conclusion is very close to being right, though - it's right if you rephrase it: "it must be possible to somehow write the product as a product of two even or two odd numbers".

You could modify your proof just slightly, and get a cleaner statement of when it is possible to do this. As you correctly point out, the sum of a+b and a-b must be even. So the two numbers a+b and a-b must either both be odd, or both be even. Thus the product (a+b)(a-b) is either odd, or it is the product of two even numbers, and is thus divisible by 4. And that's it: those are the two circumstances where it's possible to write a product of two integers as a difference of squares. Either our product must be odd, or it must be a multiple of 4. So we can do this in any of these situations:

product of two odds: e.g. 5*17 = (11 - 6)(11 + 6)
product of two evens: e.g. 14*24 = (19 - 5)(19 + 5)
product of one odd and one multiple of 4 (by moving one 2 from the even number to the odd number, to get two even numbers) : e.g. 11*16 = 22*8 = (15 + 7)(15 - 7)

and we can always do it in those situations, because when we have a product of two odds or of two evens, the median of our two numbers will always be an integer, and then we can always use the 'trick' above.

But we cannot do it in this situation:

product of one even number that is *not* divisible by 4 and one odd number: 14*5

because a^2 - b^2 must always be either odd or divisible by 4. There are a few other ways to prove that - for example, when a and b are both even, a^2 and b^2 are both divisible by 4, so a^2 - b^2 must be divisible by 4, and when a and b are both odd, you can just plug a = 2s + 1 and b = 2t + 1 into a^2 - b^2, and you'll see in that case a^2 - b^2 is also divisible by 4. So whenever a^2 - b^2 is even, it is always divisible by 4, which is what we established in a different way above.