When does  the blow-up of $CP^2$ at N points  embed in $CP^4$? Write $X_N$ for this blow up. Place the N points   in 'general position'  as needed. Then $X_6$  embeds in  $CP^2$ as a smooth cubic surface. (See, eg, Griffiths and Harris.)  But there is no other $N$ (except $N=0$)
for which   $X_N$ embeds in   $CP^3$.
(Proof: The topology of the blow-up
disagrees with that of a smooth surface of degree $d$ in $CP^3$.  (Gompf-Stipsisz p. 21.)  On the other hand, $X_N$ embeds in  $CP^5$ simply  because  any
smooth   algebraic surface $X$ so embeds. (Harris, `Algebraic Geometry, a first course', p. 193.)  
Embarrassingly, I don't even know the answer for $N=1$ where $X_1$ is  the 1st Hirzebruch surface! (I'm betting it does embed.)
Motivation: This question began in an attempt to better understand the 27 lines on the cubic
and my initial surprise at how the construction described in GH of $X_6$ yielded 
a smooth surface in $CP^3$, and how all such  surfaces arise through that construction  by varying the 6 points.  I am hoping answers might  help me   understand the moduli of blow-ups as I move the N points about the plane, and orient me as a novice to  algebraic surfaces. 
 A: For $N=1$ the answer is yes: the embedding into ${\mathbb P}^4$ is given by the linear system of conics through the blown up point (the image has degree $d=3$).
For $N=5$, the system of cubics through the 5 points gives an embedding ($d=4$).
ADDED: here are 2 slightly less obvious examples:
For $N=8$ one can take quartics with an assigned double point and 7 simple base points ($d=5$).
For $N=10$ take the quintics with 3 assigned double points and 7 simple base points ($d=6$; I did not check all the details here, because it's very boring, but I'm sure that it works).
In general, giving a satisfactory answer to your question seems very hard. There is a numerical equality,
 the so-called "double point formula" (Hartshorne, "Algebraic geometry", p.434), which is satisfied by all smooth surfaces of ${\mathbb P}^4$:
$$d^2-10d-5HK+12\chi-2K^2=0,$$
where $H$ is the hyperplane section, $d=H^2$ is the degree, $K$ is the canonical divisor and $\chi$ the Euler characteristic of ${\mathcal O}_{X_N}$.
In our case the formula becomes:
$$d^2-10d-5HK+2N-6=0.$$
In addition there is  result by G. Ellingsrud and C. Peskine [Invent. Math. 95 (1989), no. 1, 1--11] saying that  only finitely many components of the Hilbert scheme of smooth surfaces in ${\mathbb P}^4$ contain smooth rational surfaces.
 So in principle it should be possible to classify all the smooth rational surfaces in ${\mathbb P}^4$. In practice, it is known that the degree is $\le 76$, 
[Cook, An improved bound for the degree of smooth surfaces in P4 not of general type.
Compositio Math. 102 (1996)] and it is conjectured that $d\le 15$ (examples with $d=15$ do exist). There are also papers by several authors (Ranestad, Schreyer, Popescu, and others) that classify the smooth rational surfaces of ${\mathbb P}^4$ of degree $\le 11$. In these papers you can find examples of the kind you are looking for. For instance there are examples with $d=10$ and $N=18$.
A: Suppose we have a non-degenerate embedding $f:X\to \mathbb{P}^4$.  Let $L = f^\ast \mathcal{O}_{\mathbb{P}^4}(1)$, and let $V \subset H^0(L)$ be the (base-point free) $5$-dimensional linear series giving $f$.  There are two cases to consider.
Case 1:  $V = H^0(L)$ is complete.  I'm afraid here the problem seems quite difficult.  There are two essential steps.  
First, find all line bundles $L$ with $h^0(L) = 5$.  Given general points $p_1,\ldots,p_N$ and multiplicities $m_1,\ldots,m_N$, this amounts to determining the dimension of the series of curves of a given degree $d$ having singularities of multiplicity $m_i$ at $p_i$ for each $i$.  The Segre-Gimigliano-Harbourne-Hirschowitz conjecture provides an expected answer, but it is very much open.
Next, for each line bundle with $h^0(L) = 5$, we need to determine when the complete series gives an embedding.  This question has also received a lot of attention (at least in more general formulations), but at least these more general versions are still active areas of research.  A google search for ampleness of line bundles on blowups turns up many results.
Potentially an argument that tries to find some obstruction to embedding in $\mathbb{P}^4$ could sidestep this program, but being a codimension $2$ subvariety imposes much less structure than being a hypersurface.
Case 2:  $V\subset H^0(L)$ is a proper subseries.  In this case, choose a $6$-dimensional series $W$ with $V\subset W\subset H^0(L)$.  Then $W$ gives a non-degenerate embedding of $X$ in $\mathbb{P}^5$, and the embedding of $X$ in $\mathbb{P}^4$ is the composition of the embedding in $\mathbb{P}^5$ with projection from a point.  Since $V$ is base-point free, this projection is from a point lying off of the embedded surface in $\mathbb{P}^5$.  Since the projection must be an isomorphism between the two images of $X$, the secant variety of the surface in $\mathbb{P}^5$ must be a proper subvariety of $\mathbb{P}^5$.  But Severi showed the only smooth nondegenerate surface in $\mathbb{P}^5$ with deficient secant variety is the Veronese, isomorphic to $\mathbb{P}^2$ embedded by the complete series of conics.  Thus this case never actually arises.
