Yes $D$ must be finite-dimensional over $F$. This follows from a Theorem of Kaplansky's that I found in Herstein's monograph "Noncommutative Rings". The first step is to show that an algebraic algebra of bounded degree satisfies a polynomial identity (see Lemma 6.2.3 in Herstein), i.e., is a P.I. algebra. Note, however, that the degree of this polynomial identity may be larger than the degree of the algebra, as defined in the question. Then since a division algebra $D$ is primitive, one can use:
Theorem 6.3.1 (Kaplansky) If $A$ is a primitive algebra satisfying a polynomial identity of degree $d$ then $A$ is a finite dimensional simple algebra over its center, of dimension at most $\lfloor d/2 \rfloor^2$.
The theorem would still apply in the characteristic $p$ case, but as suggested in the question, it would not follow that the center of $D$ is finite-dimensional over $F$.
Edit: Kaplansky's paper can be found here: http://www.ams.org/journals/bull/1948-54-06/S0002-9904-1948-09049-8/home.html