A dice with k sides is rolled n times. The probability that there will be one pair of duplicate numbers, say for example you roll a one on the first try and a one again on another try, is given by
$P(n)=\displaystyle{1}-\frac{{{k}!}}{{{k}^{n}{\left({k}-{n}\right)}!}}$
where P(n) is the probability of a duplicate occurring after n rolls of the k-sided die, as given by the Birthday Paradox formula.
But what is the probability of there being two pairs of different duplicate numbers, say, you roll a one and a one again, as well as a three and a three again?
I've been told that I can use P(n) multiple times, one for n rolls and again for n - 2 rolls to handle the remaining cases, but it isn't perfect because those aren't independent events. Is there a better solution?
Note
I am interpreting the problem to mean that if you roll all 1's, that this does not qualify as there being at least two different numbers, each of which occurs at least twice.
Note
For convenience, I will instead compute the complementary probability that there does not exist two distinct elements in $\{1,2,\cdots,k\}$ such that each element occurred at least twice.
Then, the probability that you specifically requested will simply be $1$ minus the probability that I compute.
Initially, I considered Inclusion-Exclusion for this problem. However, the Math is just too ugly, because you are allowing one element in $\{1,2,\cdots,k\}$ to occur multiple times.
You have (in effect) already computed the probability of no duplicates, as
$$p = \frac{k!}{k^n(k-n)!}. \tag1 $$
Edit
In this question, $n$ is allowed to exceed $k$. When that happens, then the above expression should be interpreted as $p = 0$.
So, the question is, how much to add to the computation in (1) above. There are $k$ mutually exclusive cases, depending on which element from $\{1,2,\cdots,k\}$ will be the one that is permitted to repeat.
Let $A$ denote the probability that the element $(1)$ occurs multiple times, but no other element is repeated.
Then, the desired probability to add to the expression in (1) above, will be $k \times A.$
Therefore, the problem has been reduced to computing $A$.
The element $(1)$ must occur $r$ times, where $r \in \{2,3,\cdots,n\}$. Further, the other $(n-r)$ rolls must all be distinct elements, none of which are equal to $(1)$. Note that there is a second lower bound on $r$. Namely, you can not have $(k - 1) < (n - r),$ because otherwise, one of the $(n - r)$ rolls would have to violate the constraints.
Therefore, $(r)$ must be $\geq (n + 1 - k).$
So, the lower bound for $r$ will be $\max(2,n+1-k),$ and the upper bound for $r$ will be $(n)$. That is, $r = n$ represents that all $n$ rolls were a $(1)$.
Let $f(r)$ denote the probability that a $(1)$ was rolled $r$ times, and that the other $(n-r)$ rolls were all distinct numbers, none of which equaled $(1)$.
Then, $(k \times A)$, the amount to be added to the probability in (1) above, will be
$$(k \times A) = k \times \sum_{r = \max(2,n+1-k)}^n f(r). \tag2$$
Therefore, the problem has been reduced to computing $f(r)$.
I will compute
$$f(r) = \frac{N\text{(umerator)}}{D\text{(enominator)}},$$
where $D = k^n$. So, the problem of computing $f(r)$ has been reduced to enumerating the number of satisfying rolls.
There are $\displaystyle ~\binom{n}{r}~$ ways of selecting which of the rolls will be a $(1)$. Then, there are $\displaystyle ~\frac{(k-1)!}{[(k-1) - (n-r)]!}~$ ways that the other $(n-r)$ rolls can all be distinct, with none of them equaling $(1)$.
Therefore,
$$N = \binom{n}{r} \times \frac{(k-1)!}{[(k-1) - (n-r)]!}.$$
Therefore,
$$f(r) = \binom{n}{r} \times \frac{(k-1)!}{[(k-1) - (n-r)]!} \times \frac{1}{k^n}.$$
$\underline{\textbf{Putting all the pieces together}}$
$$p = \frac{k!}{k^n(k-n)!}. $$
$$f(r) = \binom{n}{r} \times \frac{(k-1)!}{[(k-1) - (n-r)]!} \times \frac{1}{k^n}.$$
$$A = ~\sum_{r = \max(2,n+1-k)}^n f(r).$$
The overall probability that there will not be two elements from $\{1,2,\cdots,k\}$ such that each of those two elements occurs at least twice is
$$p + kA.$$
Therefore, the probability that there will be at least two such elements is
$$1 - (p + kA).$$