Indeed, $\mathbf t$ corresponds to the $\mathcal T_{\mathrm{poly}}$ side (where the Poisson brackets live) and $\mathcal D_{\mathrm{poly}}$ corresponds to the natural generalization of associative deformations (where the star products live). For a smooth affine variety $M$, the Hochschild–Kostant–Rosenberg theorem gives $\mathrm{HH}^2 (M) \simeq \mathrm H^0 (\Lambda^2 \mathcal T_M)$, but for not-necessarily-affine smooth varieties one picks up extra terms:
$$
\mathrm{HH^2} (M) \simeq \mathrm{H}^0 (\Lambda^2 \mathcal T_M) \oplus \mathrm{H}^1 (\mathcal T_M) \oplus \mathrm{H}^2 (\mathcal O_M)
$$
the second summand corresponding (over $\mathbb C$) to variation of complex structures. This is why in the paper you cite Barannikov and Kontsevich relate $\mathbf t$ (which computes $\mathrm{HH}^\bullet (M)$) to the "extended moduli space of complex structures".
I think the details of the formality morphism in the algebraic setup were only worked out in later papers, and I think
is a good place to start. When $M$ is not affine $\mathrm{HH}^2 (M)$ contains not only global bivector fields, so one is naturally led to consider "extended deformations" of $M$ which Kontsevich studies under the name of "algebroid prestacks". These correspond to Abelian deformations of $\mathrm{coh} (M)$ or $\mathrm{Qcoh} (M)$, see
and they correspond to deformations of the (pre)sheaf $\mathcal O_M$ of commutative algebras as a twisted presheaf of associative algebras. For the correspondence see
Finally let me briefly address the rationale for talking about A$_\infty$ deformations of a derived category. Since $M$ is smooth, $\mathrm{D}^{\mathrm b} (\operatorname{coh} M) \simeq \mathrm D^{\mathrm{perf}} (M)$ and both are equivalent to the (perfect) derived category of a DG algebra / A$_\infty$ algebra $A$. For example, we can take $A$ to be the derived endomorphism algebra of a compact generator or its minimal model (which is an A$_\infty$ algebra). Under this correspondence deformations of $\mathrm{D}^{\mathrm b} (\operatorname{coh} M)$ can be identified (by definition, if you like) with A$_\infty$ deformations of $A$. Note that this generalizes the affine case, i.e. for $M = \operatorname{Spec} R$, deformations of $\mathrm{D}^{\mathrm b} (\operatorname{coh} M) \simeq \mathrm{D}^{\mathrm b} (R)$ correspond to A$_\infty$ deformations of $R$ which (since $R$ is not graded) are precisely associative deformations of $R$ which since $\mathrm{HH}^2 (M) \simeq \mathrm H^0 (\Lambda^2 \mathcal T_M)$ correspond precisely to quantizations of Poisson structures.