A bipartite graph $K_{m,n}$ can be embedded into a surface $S$, if $\chi (S) \leq m+n - mn/2$. 
Let $K_{m,n}$ be a complete bipartite graph.  We need to find a way to embed $K_{m,n}$ on a surface $S$. We need to show that, if
$$\chi (S) \leq m+n - \frac{mn}2\,,\tag{#}$$
then an embedding is possible.  Here, $\chi (S)$ is the Euler characteristic of the surface $S$.

By attempting at the problem, I think the converse (i.e., if there exists an embedding of $K_{m,n}$ into $S$, then (#) holds) is true.  Here is my proof (if it is correct).
Suppose that an embedding is possible.  Write $F$ for the set of all faces of $G:=K_{m,n}$.  Since a bipartite graph has no odd cycles, each face has degree at least $4$.  Therefore,
$$2|E|=\sum_{f\in F}\,\deg(f)\geq 4|F|\,,$$
where $E$ is the set of all edges of $G$.  Thus, $|F|\leq \dfrac{|E|}{2}$.  Now,
$$\chi(S)\,\overset{\color{red}{(*)}}{\color{red}{=\!=}}\,|V|-|E|+|F|\leq |V|-|E|+\dfrac{|E|}{2}=|V|-\frac{|E|}{2}\,,$$
where $V$ is the set of all vertices of $G$.  Since $|V|=m+n$ and $|E|=mn$, we obtain
$$\chi(S)\leq (m+n)-\frac{mn}{2}\,.$$
Thanks in advance.
Remark (by Batominovski).  The equality (*) is dubious, and is unlikely true.
 A: First of all, let me try to make sense of the question. A graph embeds in a planar surface if and only if it embeds in a plane.
Of course, by puncturing the plane, you can get as low Euler characteristic as you like, hence, the answer to the stated question is negative for all $m, n\ge 3$. I strongly suspect that you meant to ask about $S\subset R^3$. Of course, every open surface embeds to $R^3$, so a meaningful question would be about $S$ which is closed (compact with empty boundary) and connected. Such a surface embeds in $R^3$ if and only if it is oriented. In equivalent form, you are asking about the genus of $K_{n,m}$:
Definition. The genus $g=g(\Gamma)$ of a graph $\Gamma$ is the smallest genus of an oriented surface in which $\Gamma$ embeds.
For graphs  $K_{n,m}$ the genus is computed by Ringel's formula:
$$
g(K_{n,m})= \lceil (m-2)(n-2)/4 \rceil, 
$$
assuming $n, m\ge 2$.
In terms of the Euler characteristic, your guess is almost correct, since, assuming  $g=(m-2)(n-2)/4$ is integral,
$$
2-2g= m+n- \frac{mn}{2}. 
$$
In particular, if $K_{n,m}$ embeds in $S$, then indeed $\chi(S)\le m+n- \frac{mn}{2}$.
Edit. Ringel also proved the formula for non-orientable genus:
$$
q(K_{n,m})=\lceil (m-2)(n-2)/2 \rceil, 
$$
provided that $n, m\ge 3$. The Euler characteristic formula then is:
$$
\chi(N_q)=2-q= m+n- \frac{mn}{2}. 
$$
(assuming integrality).
Ringel's original article was in German. You can find an  English-language proof in:
André Bouchet, Orientable and nonorientable genus of the complete bipartite graph, Journal of Combinatorial Theory, Series B, Volume 24, Issue 1, February 1978, Pages 24-33.
