The maximum value is $k = 20000$. Define a region as a maximal set of same-colour squares such that there is a path of the same colour between any $2$ squares in the region. From the first condition, there is exactly one marked square in a region and so there are $k$ regions. Two regions are neighbours if they have a vertex in common.

Now suppose that $k > 20000$. Form a graph whose vertices are the regions and whose edges join neighbouring regions. Since there are only $2000$ colours, there are $2$ regions $P, Q$ with the same colour. Thus there is a path $P = A_0, A_1, \dots, A_i = Q$, with $i \ge 2000$ by the second condition. Consider the longest path in the graph: $B_0, B_1, \dots, B_j$. Then $j \ge i \ge 2000$. Suppose there is a vertex $C$ not in the path but is adjacent to a vertex $B_k$ in the path. Then $k \ne 0, j$, else there is a longer path. Consider the $2001$ vertices $C, B_p, B_{p+1}, \dots, B_{p+1999}$ where $p < k < p+1999 \le j$. Two of them have the same colour but their distance apart is $< 2000$, contradicting the second condition. So $B_0, B_1, \dots, B_j$ are all the regions and $j = k-1$. Thus to move from a square in $B_m$ to a square in $B_{m+x}$, where the index is taken mod $k$, at least $x$ moves or $k-x$ moves (if $m+x > k$) are needed. (Here a move is moving from a square to a neighbouring square.) Also $2$ neighbouring squares belong to the same region or $2$ adjacent regions.

Let $X$ be the $2 \times 2$ square in the centre of the grid. Since the $4$ squares in $X$ are mutually adjacent, $X \subseteq B_m \cup B_{m+1}$ for some $m$. Take $Y \in B_{m+\lfloor(k+1)/2\rfloor}$. Suppose the square in $X$ that is nearest to $Y$ can move to $Y$ in a minimum number of $s$ moves. Then, since that square can be in $B_m$ or $B_{m+1}$, $9999 \ge m \ge \lfloor(k-1)/2\rfloor$ or $20000 \ge k$.

There is a colouring that gives $20000$ regions. Colour all the squares in row $i$ with colour $j$ if $i \equiv j \pmod{2000}$.