Does $\aleph_0$-density of regular open algebra entail existence of countable basis?

The answer is no, not necessarily.

For a counterexample, consider the Sorgenfrey line, which is the topology on $\mathbb{R}$ with basis consisting of the half-open intervals $[a,b)$. These are each clopen and hence regular open in that topology. Furthermore, every such nonempty open interval contains a nonempty half-open interval $[p,q)$ where $p,q\in\mathbb{Q}$, and so the regular open algebra is $\aleph_0$-dense as a Boolean algebra. The Sorgenfrey line is normal but not second-countable. Thus, it serves as a counterexample to your question.

For the last part of the question, this gives an example where the cardinality of the excess not covered has size continuum.

Joel has already shown you that none of the standard separation axioms is enough to force a positive answer to your question (by the way, the Sorgenfrey line is even perfectly normal).

A notable case for which your question has a positive answer is that of a topological group.

Define the $\pi$-weight of $X$ ($\pi w(X)$) to be the least cardinality of a family $\mathcal{P}$ of non-empty open subsets of $X$ such that for every non-empty open set $U \subset X$ there is $P \in \mathcal{P}$ such that $P \subset U$. It is clear that if $RO(X)$ is a base for $X$ then the density of $RO(X)$ coincides with the $\pi$-weight of $X$. This happens, in particular, if $X$ is a regular space. Now topological groups are regular, and the $\pi$-weight and the weight of a topological group coincide.

(for a proof of that see, for example, Arhangel’skii, Alexander; Tkachenko, Mikhail, Topological groups and related structures, Atlantis Studies in Mathematics 1. Hackensack, NJ: World Scientific; Paris: Atlantis Press (ISBN 978-90-78677-06-2/hbk). xiv, 781 p. (2008). ZBL1323.22001.)

Another case in which $\pi w(X)=w(X)$ is when $X$ is a metric space (because the $\pi$-weight is bounded below by the density and bounded above by the weight, and for metric spaces, the weight and the density coincide).