I will only give some simple and useful estimate (confirmed by numerical results, based on some mathematical idea). It is essentially a lower bound, but can probably be easily modified to be an upper bound. Moreover, it might give you further ideas.
Denote your expression by $\varphi_n$, and consider a random variable $X$ with binomial$(n,1/2)$ distribution. Then
$$
{\rm E}\big[2^{\sqrt X } \big] = \sum\limits_{k = 0}^n {2^{\sqrt k } {n \choose k}\frac{1}{{2^n }}} = \frac{1}{{2^n }}\varphi _n.
$$
The left-hand side is actually the moment-generating function $M(t)$ of $\sqrt{X}$ at $t=\ln2$, but we will not use this fact.
I have plotted the function $2^{\sqrt{x}}$, $x > 0$, and it seems that this function is typically convex (it is not convex near $0$). So, heuristically, Jensen's inequality suggests the following result:
$$
{\rm E}\big[2^{\sqrt X } \big] > 2^{\sqrt {{\rm E}[X]} },
$$
for all sufficiently large $n$. (If $n$ is large, then $X$ typically takes values in a set on which $2^{\sqrt{x}}$ is convex.) Finally, ${\rm E}[X]=n/2$ leads to $2^{ - n} \varphi _n > 2^{\sqrt {n/2} }$, that is
$$
\sum\limits_{k = 0}^n {{n \choose k} 2^{\sqrt k } } > 2^{n + \sqrt {n/2} },
$$
for all sufficiently large $n$. Numerical results indicate that this inequality holds for all $n \geq 6$. Moreover, the results suggest that the (lower-)bound is quite tight (I checked for $n \leq 150$). So, a tight upper-bound is likely to be something not far from $2^{n + \sqrt {n/2}}$.
EDIT: We can also employ the strong law of large numbers (SLLN) to show that $\varphi_n$ may be expected to behave something like $2^{n + \sqrt {n/2}}$ for large $n$. Indeed, writing $X$ as $Y_1 + \cdots + Y_n$, where $Y_i$ are i.i.d. rv's with ${\rm P}(Y_i = 0) = {\rm P}(Y_i = 1) = 1/2$, we have
$$
\varphi _n = 2^n {\rm E}\bigg[2^{\sqrt n \sqrt {\frac{{Y_1 + \cdots + Y_n }}{n}} } \bigg].
$$
By SLLN, $\frac{{\sum\nolimits_{i = 1}^n {Y_i } }}{n}$ converges to $1/2 \,(= {\rm E}[Y_1])$ almost surely, and the conclusion follows.