show/hide this revision's text 3 added 319 characters in body

Here is a little data (not an answer) for small arrays for anyone who wants to compare against a theoretical calculation. I looked at square $n \times n$ arrays, $k=2$ colors only. Here are the counts for $P$, after $100$ random trials: $$ (2, 2.4), (3, 24.2), (4, 95.5), (5, 260.3), (6, 575.0), (7, 1100.1), (8, 1919.0) $$ In other words, just to interpret the last piece of data: In random $8 \times 8$ arrays, of the $\binom{64}{2}=2016$ pairs, there were on average $T=97.0$ distinct distance/color pairs (using Gerhard's definition for types $T$), leaving $P=1919.0$ repeated pairs; note $T+P=2016$. (In one trial, the distance $\sqrt{65}$ and colors $(2,2)$ occurred only once, whereas the distance $\sqrt{41}$ and colors $(1,2)$ occurred $25$ times.) Here is a graph of the same data:
          Coloring Lattice Plot

Added. Now that the OP has indicated an interest in variation with the number of colors $k$, here is the same type of data, but for $k=2,3,4,5,6$:
          2,3,4,5,6 colors
show/hide this revision's text 2 Revised according to clarification of $P$.; added 15 characters in body

Here is a little data (not an answer) for small arrays for anyone who wants to compare against a theoretical calculation. I looked at square $n \times n$ arrays, $k=2$ colors only. Here are the mean counts , for $P$, after $100$ random trials, of the average number of pair/color counts, which I interpret as $P$ in the original question: $$ (2, 1.80)2.4), \; (3, 3.01)24.2), \; (4, 4.95)95.5), \; (5, 7.55)260.3), \; (6, 11.48)575.0), \; (7, 15.49)1100.1), \; (8, 20.831919.0) $$ In other words, just to interpret the last piece of data: In random $8 \times 8$ arrays, of the $\binom{64}{2}=2016$ pairs, the there were on average number of repeats of the same distance and the same two colors is $20.83$. T=97.0$ distinct distance/color pairs (using Gerhard's definition for types $T$), leaving $P=1919.0$ repeated pairs; note $T+P=2016$. (In one trial, the distance $\sqrt{65}$ and colors $(2,2)$ occurred only once, whereas the distance $\sqrt{41}$ and colors $(1,2)$ occurred $25$ times.) Here is a graph of the same data:
          Coloring Lattice Plot
show/hide this revision's text 1

Here is a little data (not an answer) for small arrays for anyone who wants to compare against a theoretical calculation. I looked at square $n \times n$ arrays, $k=2$ colors only. Here are the mean counts, after $100$ random trials, of the average number of pair/color counts, which I interpret as $P$ in the original question: $$ (2, 1.80), \; (3, 3.01), \; (4, 4.95), \; (5, 7.55), \; (6, 11.48), \; (7, 15.49), \; (8, 20.83) $$ In other words, just to interpret the last piece of data: In random $8 \times 8$ arrays, of the $\binom{64}{2}=2016$ pairs, the average number of repeats of the same distance and the same two colors is $20.83$. (In one trial, the distance $\sqrt{65}$ and colors $(2,2)$ occurred only once, whereas the distance $\sqrt{41}$ and colors $(1,2)$ occurred $25$ times.) Here is a graph of the same data:
          Coloring Lattice Plot