This is a very important issue that is usually overlooked in almost all books even if it being of fundamental relevance in my view. Also with a great impact on the quantization procedure. (Also for other fields than Maxwell one
According to the original issue, we end up with this set of differential equations (I henceforth assume $c=1$)
$$
\nabla\cdot\mathbf A = - \frac{\partial \phi}{\partial t} \tag{1}
$$
$$
\Box \mathbf A = -\mu_0 \mathbf J \tag{2}$$ $$
\Box \phi = -\frac{\rho}{\varepsilon_0}. \tag{3}
$$
They have to be solved simultaneously. As already noticed in @Sanchar's answer, the second pair of equations implies
$$ \square \left( \boldsymbol{\nabla}\cdot\boldsymbol{A} +\frac{\partial \phi}{\partial t} \right) = -\mu_0 \boldsymbol{\nabla}\cdot\boldsymbol{J} - \frac{\partial_t\rho}{\varepsilon_0} = 0, \tag{4}$$
when one assumes that the continuity equation of the electric charge is valid, and this can be done with a suitable choice of the given sources $\rho$ and $J$.
It is not possible at the level of equations to get anything stronger than (4), in place of the wanted (1).
In summary, we cannot assume from scratch that the gauge condition (1) is satisfied by solutions of (2) and (3) with given $\rho$, $J$. Even if they satisfy the continuity law of the electric charge!
The only place where we can impose some further constraint in order to get (1) satisfied is while giving the initial conditions for the fields $\phi$ and ${\bf A}$.
To see how this machinery works, let me remind a fundamental theorem of existence and uniqueness for 2nd order hyperbolic differential equations specialized to the n+1 dimensional Minkowski spacetime and for the D'Alemebert equation (it can be formulated into a generalized version in any globally hyperbolic spacetime for normally hyperbolic PDEs).
THEOREM 1 Consider the system of PDEs for the vector valued function $\Phi \in C^\infty(\mathbb{R}\times \mathbb{R}^n; \mathbb{R}^k)$
$$-\frac{\partial^2 \Phi}{\partial t^2} + \Delta_{\vec{x}}\Phi = F(t,\vec{x}) \tag{E}$$
where $F \in C^\infty(\mathbb{R}\times \mathbb{R}^n; \mathbb{R}^k)$ is known and has compact support on every surface $t=t_0$. If
$$\Phi(0, \vec{x}) = \Phi_0(\vec{x})\:, \quad \forall \vec{x} \in \mathbb{R}^n\tag{BC1}$$
and
$$(\partial_t\Phi)(0, \vec{x}) = \Pi_0(\vec{x})\:, \quad \forall \vec{x} \in \mathbb{R}^n\tag{BC2},$$ where $\Phi_0,\Pi_0 \in C^\infty(\mathbb{R}^n; \mathbb{R}^k)$
are given compactly supported functions, then there exists a unique solution of the Cauchy problem (E)-(BC1)-(BC2).
The condition on the supports of the source $F$ and the initial conditions can be relaxed, but I will deal with this basic case.
Now consider the system (1)-(3). If we define $\Phi = (\phi, {\bf A})$ we can exploit Theorem 1 to prove that a solution of the system (2)-(3) exists and is unique for every choice of the initial conditions $$\phi(0, \cdot)=: \phi_0(\cdot)$$ $$\partial_t \phi(0, \cdot)=: \pi_0(\cdot) $$ $$A(0, \cdot)=: A_0(\cdot) $$ $$\partial_t A(0, \cdot)=: \Pi_0(\cdot)$$
If we wish that also (1) be valid, we can exploit Theorem 1 again for the scalar $G:= \boldsymbol{\nabla}\cdot\boldsymbol{A} + \frac{\partial \phi}{\partial t}$.
This should amount to impose some constraints on the initial conditions written above!
However, apparently, a problem pops out here. Because, to have that (1) is valid for all times as a consequence of THeorem 1 (applied to $\Phi=G$), we must impose two initial conditions.
Evidently one is
$$G(0, \vec{x})=0 \quad \mbox{that is} \quad \boldsymbol{\nabla}\cdot\boldsymbol{A} + \frac{\partial \phi}{\partial t}=0 \quad \mbox{for $t=0$}$$
The other should be the first time derivative of it
$$(\partial_t G)(0, \vec{x})=0 \quad \mbox{that is} \quad \boldsymbol{\nabla}\cdot\boldsymbol{\partial_t {\bf A}} + \frac{\partial^2 \phi}{\partial t^2}=0 \quad \mbox{for $t=0$}\:.\tag{S}$$
The problem is that here the constraint is imposed on the second $t$-derivative of $\phi$ and we cannot arbitrarily fix it! We can only fix the fields at $t=0$ and their first $t$-derivatives at $t=0$.
However we have to keep in our mind that (S) does not come alone, but it is imposed together with (1),(2) and (3). In particular (3) yields (I assumed $c=1$)
$$\frac{\partial^2\phi}{\partial t^2} = \Delta_{\vec{x}} \phi + \frac{\rho}{\epsilon_0}$$
Summing up, our initial Cauchy problem (1)-(2)-(3) yields the system
$$
\Box\left(\nabla\cdot\mathbf A + \frac{1}{c^2}\frac{\partial \phi}{\partial t}\right)=0 \tag{G2}
$$
$$
\Box \mathbf A = -\mu_0 \mathbf J $$ $$
\Box \phi = -\frac{\rho}{\varepsilon_0}.
$$
with initial conditions
$$\phi(0, \cdot)=: \phi_0(\cdot)$$ $$\partial_t \phi(0, \cdot)=: \pi_0(\cdot) $$ $$A(0, \cdot)=: A_0(\cdot) $$ $$\partial_t A(0, \cdot)=: \Pi_0(\cdot)$$
If these initial conditions satisfy the constraints
$$\boldsymbol{\nabla}\cdot\boldsymbol{A}_0(\vec{x}) + \pi_0(\vec{x})=0 \qquad that \: is\: G(0, \vec{x})=0 \quad for \: t=0\tag{C1}$$
and
$$\boldsymbol{\nabla}\cdot\boldsymbol{{\bf \Pi}_0}(\vec{x}) + \Delta_{\vec{x}} \phi_0(\vec{x}) + \frac{\rho(0,\vec{x})}{\epsilon_0}=0 \quad that\: \: is \:(\partial_t G)(0,\vec{x})=0 \: for \:t=0\:,\tag{C2}$$
Theorem 1 guarantees that there exists exactly one solution of the equation of motion and of the gauge constraint. If it happens, as the unique solution of (G2) with vanishing initial conditions guaranteed by the constraints (C1) and (C2) is $G\equiv 0$, we have found a (unique) solution of the initial gauged problem (1)-(2)-(3).
If the constraints (C1) and (C2) are not satisfied on the initial conditions of (1)-(3) -- as they arise from the request that $G=0$ at every time -- there is no solution of the system (1)-(2)-(3).
In summary, assuming the validity of the continuity of the electric charge, the answer to the initial question is the following one.
There is a (uniquely determined) solution of the Maxwell equations together with the validity of the (Lorenz) gauge condition if and only if the initial conditions of the fields $\phi$ and ${\bf A}$ satisfy some constraints. If these constraints are not fulfilled, there are no solutions of the overall problem.