In $\mathbb{R}^3$, $dB=0$ implies $B=dA$ by Poincaré's lemma. In vector terms, this means that $\nabla\cdot B=0$ implies $B=\nabla \times A$.
However, by Helmholtz decomposition we have $B=\nabla \times C+\nabla \phi$ and the condition $\nabla\cdot B=0$ does not force $\phi=0$ but rather $\nabla^2\phi=0$.
I am not sure how to reconcile Poincaré with Helmholtz.
A divergence-free vector field must be a curl or could it be a curl plus the gradient of a harmonic function?
Just to expand on Cave Johnson's comment, note that if $\mathbf{A}$ is such that $\mathbf{B}=\nabla\times \mathbf{A}$, the for any scalar $\chi$, the vector field $\mathbf{A}'=\mathbf{A}+\nabla \chi$ also has $\mathbf{B}=\nabla \times \mathbf{A'}$. Physcists (and nowadays mathematicians too) call the transformations $\mathbf{A}\to \mathbf{A'}=\mathbf{A}+\nabla \chi$ a gauge transformation and the vector field $\mathbf{B}$ (magnetic field) is gauge invariant.
Now about Helmholtz decompositions. Suppose $\mathbf{B}=\nabla \times \mathbf{C}+\nabla \phi$. Suppose there exists scalar field $f$ and a vector field $\mathbf{F}$ such that $$ \nabla f = \nabla\times \mathbf{F} $$ Then $\mathbf{C}'=\mathbf{C}+\mathbf{F}$ and $\phi'=\phi-f$ also satisfies $\mathbf{B}=\nabla \times \mathbf{C}'+\nabla \phi'$. If the above condition holds, than clearly $\nabla^2 f=0$ and $f$ is harmonic. Conversely, as Cave Johnson mentions, if $f$ is a harmonic function, then $\nabla f =\nabla\times \mathbf{F}$ for some vector field $\mathbf{F}$. The proof of this is Poincare lemma and is exactly the reconciliation you are looking for between Poincare lemma and Helmholtz decomposition.
Combining all of this together, for any harmonic function $f$, with some $\mathbf{F}$ such that $\nabla f = \nabla \times \mathbf{F}$, and any arbitrary scalar field $g$, the (gauge?) transformations $$ \mathbf{C}\to \mathbf{C}'=\mathbf{C}+\nabla g +\mathbf{F}, \quad \phi\to \phi'=\phi-f $$ yield all possible different Helmholtz decompositions of $\mathbf{B}$.