Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$
The answer depends on the exact computation model and on the representation of the input. But here is one way to check whether a given subset is a vertex cover, assuming the graph is represented using adjacency lists.

Let the purported vertex cover be $S$, of size $k$. Start by counting all edges in $G$, stopping once you reach $kn$. If there are more than $kn$ edges, then $S$ is not a vertex cover, and we can stop. In time $O(|E|) = O(kn)$, you can count (1) $\sum_{i \in S} \deg(i)$ and (2) the number of edges connecting vertices in $S$. The total number of edges covered by $S$ is the difference between these two numbers, which you can compare to $|E|$.