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$.