Another version of the 3-coloring decision problem?
Note that when $k$ is a fixed constant (that is, $k$ is not part of the input, for example $k = 17$ ), then the problem is easy. Indeed, in this case, your suggestion works because $n \choose l$ is polynomial in $n$, for every $l\leq k$. Also, checking whether a graph is bipartite can be done in polynomial time.
If $k$ is part of the input, then your problem is harder than the NP-complete vertex-deletion graph bipartization problem. The later problem is defined as follows. Given a graph $G$ and an integer $k\geq 0$, find a subset of at most $k$ vertices such that removing these vertices results in a bipartite graph.
To see why your problem is harder, assume that you have indeed succeeded in coloring a graph with $c_1, c_2$ and $c_3$, where at most $k$ vertices are colored with $c_1$. Then, removing the vertices that are colored with $c_1$ leaves us with a subgraph colored with $c_2$ and $c_3$, and thus the remaining subgraph has to be bipartite as two vertices with same color cannot be neighbors.
The vertex-deletion graph bipartization problem is known to be NP-complete even when restricted to planar graphs. See here.