Given your boundary conditions, if we open up the recurrence relation then we discover an $m$-step process, where at each step we change $n$ by $0$ or $\pm 1$. For every walk that ends up at $0$, we "score" one point.
How many such walks exist? There is an equal number $k$ of $+1$s and $-1$s, and so we get
$\displaystyle \sum_{k=0}^{\lfloor m/2 \rfloor} \binom{m}{k,k} = \sum_{k=0}^{\lfloor m/2 \rfloor} \frac{m!}{k!k!(m-2k)!}$
In order to estimate it, let's calculate the largest coefficient, assuming $m$ is divisible by $3$. It is
$\displaystyle \frac{m!}{(m/3)!} \approx \frac{\sqrt{2\pi m}(m/e)^m}{\sqrt{2\pi (m/3)}^3 (m/3e)^m} = \frac{3^m}{(2\pi/3^{1.5})m}$
Roughly, we expect about $O(\sqrt{m})$ of the summands to be of comparable size, so a conjectured upper bound would be $O(3^m/\sqrt{m})$.