1)
We will count value $S$, the number of the tuples $(A, B, C)$ with column $A, B$ and row $C$ in relation $A-C, B-C$ intersect at the colored cell.

First way, denote $x_{i}$ as the number of colored cells on the $i$th row, then
$$S = \sum_{i=1}^{p^{2}+p+1} \binom{x_{i}}{2}.$$

Second way, choose two columns among $p^{2}+p+1$ columns, we have $\binom{p^{2}+p+1}{2}$ ways. And then, we have at most 1 row $C$ that cuts $A, B$ at two colored cells (since there are no rectangle), then
$$S \leq \binom{p^{2}+p+1}{2}.$$

Notice that $\sum_{i=1}^{p^{2}+p+1} x_{i} = k$. Hence, we have
$$\binom{p^{2}+p+1}{2} \geq \sum_{i=1}^{p^{2}+p+1} \binom{x_{i}}{2} \geq \frac{1}{2}\left(\frac{1}{p^{2}+p+1} k^{2} - k\right)$$
or $k \leq (p+1)(p^{2}+p+1)$.

2)
Consider the tuples $(a, b, c)$ in which $0 \leq a, b, c \leq p-1$ and $a+b+c>0$, then we have $p^{3}-1$ tuples in total.

Since two tuples $(a, b, c)$ and $(d, e, f)$ are considered to belong to the same set if and only if $\exists k \in \{1,2,3, \ldots, p-1\}$ such that $a \equiv k d, b \equiv k e, c \equiv k f \pmod{p}$. We have $p-1$ ways to choose $k$, then $\frac{p^{3}-1}{p-1} = p^{2}+p+1$ sets satisfy the given condition.

3)
From the way to color the table, one can check that on each row, there are exactly $p+1$ colored cells. Indeed, we need to prove that $a x + b y + c z \equiv 0 \pmod{p}$ has exactly $p+1$ solutions that do not belong to the same set $S_{1}, S_{2}, \ldots, S_{p^{2}+p+1}$.

There are $p^{2}-1$ pairs $(x, y)$ and for each pair, there is a unique number $z$ such that $a x + b y + c z$ is divisible by $p$. Each set has $p-1$ solutions, then there are $p+1$ solutions that do not belong to the same set. Multiply this number with the number of columns, we have verified that there are $(p+1)(p^{2}+p+1)$ colored cells on the table.

Then, we shall prove that there are no rectangles. For two tuples $(a, b, c)$ and $(d, e, f)$ that do not belong to the same set, we need to prove that the following system of equations has no more than one solution:
$$\begin{cases} a x + b y + c z \equiv 0 & (\bmod p) \\ d x + e y + f z \equiv 0 & (\bmod p) \end{cases}$$
Without loss of generality, we can suppose that $\frac{b}{e} - \frac{c}{f}$ is not divisible by $p$ or $b f \not\equiv c e \pmod{p}$, then for all $x_{0} = 1, \ldots, p-1$, there is exactly one value $y_{0}, z_{0}$ such that
$$b y_{0} + c z_{0} = a x_{0}, \quad e y_{0} + f z_{0} = d x_{0} \pmod{p}.$$
On the other hand, there are $p$ values $x_{0}$ and we do not consider the tuple $(0,0,0)$, then there are at most $p-1$ solutions.

Note that if $(x, y, z)$ is a solution, then so is $(k x, k y, k z)$, then the above system has no more than one solution.

This finishes our proof and $k_{\text{max}} = (p+1)(p^{2}+p+1)$.