A proper colouring $V(G) \to \{1,...,k\}$ of a graph $G$ is complete if every distinct pair of colours is connected by an edge. What is the least $n_k$ such that there exists a planar graph on $n_k$ vertices with a complete $k$-colouring?
Such a graph must have at least $\binom k2$ edges, and but because it is planar it can have no more than $3n-6$ edges, so immediately we get a naive bound $n_k\ge\bigl\lceil\tfrac{k(k-1)}6+2\bigr\rceil$ (for $k\ge3$). But this bound isn't always attainable:
Suppose there exists a complete 6-colouring on a graph with $\bigl\lceil\tfrac{6\cdot5}6+2\bigr\rceil=7$ vertices. By the pidgeonhole principle, some pair of vertices must have the same colour, and upon their removal you'd have a complete 5-colouring of a 5-vertex graph—but this can only be the complete graph $K_5$, which is nonplanar. So $n_6>7$.
The first few values of $n_k$ are 1, 2, 3, 4, 6, 8, 10, 12. Can $n_k$ be determined exactly for all $k$? Failing that, are there better bounds than the quick and dirty ones below? $$\bigl\lceil\tfrac16k(k-1)+2\bigr\rceil\le n_k\le\bigl\lfloor\tfrac14k^2\bigr\rfloor \quad \text{(for $k\ge4$)}$$
Your question your may be rewritten as:
For each $k$, what is the smallest number $n$, such that there exists a planar graph $G$ having $n$ vertices and $\psi(G)=k$, where $\psi$ indicates the graph's pseudochromatic number.
As far as I know there does not exist an explicit formula for the sequence you asked about. However, some stronger bounds may be found here. For example, using your notation, in the article we may find that: $$k \leq \Big\lfloor \sqrt{2n_k+\frac{1}{4}} +\frac{1}{2}\Big\rfloor$$