Here is a later review of my previous answer, as promised (the original, left in the bottom, had a flaw, as you pointed out in comment).
I know from the comments there is already a clear reference to other answers, but I did not want to leave here an incomplete (accepted and rewarded) answer.
I will need the two following Lemmas.
Lemma 1. If $C_1 \supset C_2$ are elements of $\mathcal A$, then $d_{\mathcal A}(C_1,C_2) = \max_{x \in C_1}[\min_{y \in C_2}(x,y)]$.
Proof. $\forall y \in C_2$ we have that $\min_{x \in C_1}(x,y) = 0$. Therefore $\max_{y\in C_2}[\min_{x\in C_1}(x,y)]=0$. $\square$
Lemma 2. If $C_1 \supset C_2\supset \cdots$ is a nested sequence of elements of $\mathcal A$, and $$C= \bigcap_{n=1}^\infty C_n,$$then the sequence $(C_n)$ converges to $C$, that is $$\lim_{n\to \infty} d_{\mathcal A}(C_n,C) = 0.$$
Proof. (Note that $C$ is not empty.) Suppose, by contradiction, that there exists $\varepsilon >0$ such that, for all $n>0$, we have $d_A(C_{p_n},C)> \varepsilon$, for some $p_n>n$. By Lemma 1, this means that there exists an element $c_{p_n} \in C_{p_n}$ such that $\min_{y \in C}d(c_{p_n},y) > \varepsilon$. This implies that
$$d(c_{p_n},y)> \varepsilon, \ \ \forall y\in C.$$
Since the sequence $(c_{p_n})$ is bounded, it must have a converging subsequence. Let us call it $(\gamma_n)$. Suppose $(\gamma_n) \to \gamma$. What we have stated guarantees that $\gamma \not \in C$, that is $$\gamma \in U =\overline{\bigcap_{n=N}^\infty C_n}$$
for some $N>0$. $U$ is an open set. Thus there exists an open neighborhood of $\gamma$ entirely contained in $U$. This, however, implies that $(\gamma_n)\not \to \gamma$, a contradiction. $\square$
Now we have what we need to prove that $(\mathcal A, d_{\mathcal A})$ is complete.
Consider a Cauchy sequence $(B_n)$. We want to construct a subsequence that is convergent. This will imply convergence of $(B_n)$.
At this aim, let $B_{p_1}$ an element of the sequence such that
$$d_{\mathcal A}(B_{p_1},B_m) < \frac12, \ \ \forall m> p_1,$$
and let
$$\tilde C_1 = \mbox{cl}\left(\bigcup_{x\in B_{p_1}}N_{\frac12}(x)\right),$$
where $\mbox{cl}(\cdot)$ denotes closure and $N_r(x) = \{y \in D : d(x,y) < r\}$ is the open neighbourhood of $x$ with radius $r$. Observe that
$$B_m \subset \tilde C_1, \ \ \forall m > p_1.$$
Now choose $p_2 > p_1$ in such a way that
$$d_{\mathcal A}(B_{p_2},B_m)< \frac14, \ \ \forall m>p_2, $$
and, correspondingly
$$\tilde C_2 = \mbox{cl}\left(\bigcup_{x\in B_{p_2}}N_{\frac14}(x)\right).$$
We have now that
$$B_m \subset \tilde C_1 \cap \tilde C_2, \ \ \forall m>p_2.$$
Proceed iteratively like that for $n=1,2,3,\dots$. Therefore, select $B_{p_n}$ so that $p_n>p_{n-1}$ and
$$d_A(B_{p_n},B_m)< \frac1{2^n}, \ \ \forall m>p_n$$
and construct closed
$$\tilde C_n = \mbox{cl}\left(\bigcup_{x\in B_{p_n}}N_{\frac1{2^n}}(x)\right),$$
so that
$$B_m \subset C_n = \bigcap_{k=1}^n \tilde C_n, \ \ \forall m>p_n.$$
Observe that, by construction,
$$d_{\mathcal A}(B_{p_n},C_n) \leq \frac1{2^n},$$
and therefore, by triangle inequality,
$$d_{\mathcal A}(B_{p_m},C_n) \leq d_{\mathcal A}(B_{p_m},B_{p_n}) + d_{\mathcal A}(B_{p_n},C_n) < \frac1{2^{n-1}}, \ \ \forall p_m> p_n.$$
Recall also that, by Lemma 2,
$$\lim_{n\to \infty} d_{\mathcal A}(C_n,C) = 0,$$
where
$$C = \bigcap_{n=1}^\infty C_n.$$
We want to show that $(B_{p_n})$ converges to $C$. Fix $\varepsilon > 0$. For $k> N_1$,
$$d_{\mathcal A}(C_k,C)< \frac{\varepsilon}{2}.$$
For $k>2-\log_2\varepsilon$,
$$d_{\mathcal A}(B_{p_n},C_k) < \frac{\varepsilon}{2}, \ \ \forall p_n > k.$$
Thus
$$d_{\mathcal A}(B_{p_n},C) \leq d_{\mathcal A}(B_{p_n},C_k) + d_{\mathcal A}(C_k,C) < \varepsilon,$$
for $p_n > \max(N_1,2-\log_2\varepsilon)$. Since $(B_{p_n})$ converges to $C$ and it is a subsequence of a Cauchy sequence, it follows that $(B_n)$ converges also to $C$. The thesis follows. $\square$
ORIGINAL ANSWER.
I think your proof is correct.
As for the completeness of $(A,d_A)$, I would proceed as follows. I am pretty sure there are simpler proofs. Have a look; and let us see, in the meantime, what the community suggests.
Consider, as you said, a Cauchy sequence $(B_n)$. We want to construct a subsequence that is convergent. This will imply convergence of $(B_n)$.
At this aim, let $B_{p_1}$ an element of the sequence such that
$$d_A(B_{p_1},B_m) < \frac12, \ \ \forall m> p_1,$$
and let
$$\tilde C_1 = \mbox{cl}\left(\bigcup_{x\in B_{p_1}}N_{\frac12}(x)\right),$$
where $\mbox{cl}(\cdot)$ denotes closure and $N_r(x) = \{y \in D : d(x,y) < r\}$ is the open neighbourhood of $x$ with radius $r$. Observe that
$$B_m \subset \tilde C_1, \ \ \forall m > p_1.$$
Now choose $p_2 > p_1$ in such a way that
$$d_A(B_{p_2},B_m)< \frac14, \ \ \forall m>p_2, $$
and, correspondingly
$$\tilde C_2 = \mbox{cl}\left(\bigcup_{x\in B_{p_2}}N_{\frac14}(x)\right).$$
We have now that
$$B_m \subset \tilde C_1 \cap \tilde C_2, \ \ \forall m>p_2.$$
Proceed iteratively like that for $n=1,2,3,\dots$. Therefore, select $B_{p_n}$ so that $p_n>p_{n-1}$ and
$$d_A(B_{p_n},B_m)< \frac1{2^n}, \ \ \forall m>p_n$$
and construct closed
$$\tilde C_n = \mbox{cl}\left(\bigcup_{x\in B_{p_n}}N_{\frac1{2^n}}(x)\right),$$
so that
$$B_m \subset C_n = \bigcap_{k=1}^n \tilde C_n, \ \ \forall m>p_n.$$
Observe that, by construction,
$$d_A(B_{p_n},C_n) \leq \frac1{2^n},$$
and, by triangle inequality,
$$d_A(B_{p_m},C_n) \leq d_A(B_{p_m},B_{p_n}) + d_A(B_{p_n},C_n) < \frac1{2^{n-1}}, \ \ \forall p_m> p_n\tag{1}\label{tri}$$
Since the sets $C_n$ are closed (and therefore compact) and $C_1 \supset C_2 \supset C_3 \dots$, we have that
$$C = \bigcap_{i=1}^\infty C_i \neq \emptyset.$$
We want now to show that the sequence $(B_{p_n})$ converges to $C$. Suppose, by contradiction, that there exists $\varepsilon >0$ such that, for all $N>0$, there is $p_m> N$ for which $d_A(B_{p_m},C)>\varepsilon$, implying, by definition, $\max_{c \in C} [\min_{b\in B_{p_m}}(b,c)]> \varepsilon$. This means that there exists $c\in C$ such that $\min_{b\in B_{p_m}}d(b,c)>\varepsilon$. Select $n$ large enough that $\varepsilon > \frac1{2^{n-1}}$. We have that $c \in C_n$, and, thus
$$d_A(B_{p_m},C_n) = \max_{c\in C_n}[\min_{b\in B_{p_m}}(b,c)]>\varepsilon > \frac1{2^{n-1}}.$$
Recall that there exists such $p_m >N$ for arbitray choice of $N$. So taking $N>p_n$ contradicts \eqref{tri}. Hence
$$(B_{p_n}) \to C,$$
and, since $(B_n)$ is Cauchy,
$$(B_n)\to C.$$
