What is the probability that two numbers between 1 and 10 picked at random sum to a number greater than 5?

In this case, it is easier to find the probability $p$ that the sum is $\le 5$. Then the answer to the original problem is $1-p$.

We can list and count the ordered pairs $(a,b)$ of numbers that have sum $\le 5$.

If $a=1$ there are $4$, if $a=2$ there are $3$, and so on down to $1$.

So there are $10$ ordered pairs. Each has probability $\frac{1}{10^2}$, so $p=\frac{10}{10^2}$.

Remark: The same idea will work in your general case, as long as $k\le n+1$. A modification will take care of the rest of the $k$.

I would start with looking at each case and then derive the probability: The first column states the number at first pick, and the second the number that is needed at least during 2nd pick to have $>5$. The third shows the probability for the given case:

1  5 = 1/10 * 6/10
2  4 = 1/10 * 7/10
3  3 = 1/10 * 8/10
4  2 = 1/10 * 9/10
5  1 = 1/10 * 10/10
6  0 = 1/10 * 10/10
7  0 = 1/10 * 10/10
8  0 = 1/10 * 10/10
9  0 = 1/10 * 10/10
10 0 = 1/10 * 10/10

So the whole probability is

$p = 6/100 + 7/100 + 8/100 + 9/100 + 6 * 1/10 = 9/10$

From this, you can derive a general formula for arbitrary $n$ and $k$:

$p = {1\over n^2} ((k + 1) + \dots + n) = {n^2-{k(k-1)\over2}\over n^2} = 1 -{k(k-1) \over 2n^2}$

You could solve this with generating functions. The generating function for this situation, equivalent to rolling a fair 10-sided die twice, is:

$$(x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10})^2$$

which expands to

$$x^2 + 2 x^3 + 3 x^4 + 4 x^5 + 5 x^6 + 6 x^7 + 7 x^8 + 8 x^9 + 9 x^{10} + 10 x^{11} + 9 x^{12} + 8 x^{13} + 7 x^{14} + 6 x^{15} + 5 x^{16} + 4 x^{17} + 3 x^{18} + 2 x^{19} + x^{20}$$

The coefficient of each $x^n$ is the number of ways of getting a sum of $n$ from the two random draws. There are 100 total possibilities ($10 \cdot 10$) with two draws from 1...10 with replacement. Looking at the polynomial above, the coefficients of the monomials $x^2$ through $x^5$ show that there are a total of 10 ways to get a sum of 5 or less. Thus, the probability of a sum greater than 5 is 90/100 or 0.9.

Perhaps a simpler way is to first eliminate the cases where at least one draw is 5 or greater, since these guarantee a sum greater than five. There are 84 of these, leaving only the 16 cases in which both draws are 4 or less. This can also be done with a generating function (though counting manually is easy too):

$$(x + x^2 + x^3 + x^4)^2 = x^2 + 2 x^3 + 3 x^4 + 4 x^5 + 3 x^6 + 2 x^7 + x^8$$

once again giving 10 out of 100 cases where the sum is 5 or less.