I'll restrict myself to answer
Blockquote My question: Could the electric dipole moment of the neutron $d_n$ be used to effectively detect the CP violating $\theta$? If not, then is there really a strong CP problem?
In these lectures on the CP Problem or this SE post you can see how you can relate the value of of the theta angle $\theta$ to the value of the neutron eDM. A priori it should be possible to obtain a similar result for the proton but, as far as I know, we mostly focus on the neutron eDM because it is easier to measure. So, even if there were no $d_n$, you could still have other similar magnitudes that are not null.
But OK, let's imagine that there is some mechanism that suppresses all QCD eDMs (and other CP-violating quantities) without that requiring a non-null $\bar{\theta}$. Could we still have a CP problem? Well, it could still be that QCD does not violate CP-symmetry, but we would not be able to measure it experimentally, so we would lose all experimental justification to search for reasons that drive $\bar{\theta}$ to be small! This doesn't mean that axions, or whatever other solution to the Strong CP problem, don't exist. We would have just lost the biggest reason to believe they exist (there are others, as we think axions might be cold dark matter, see this again).
Just as a side note, in the preprint you're mentioning, the author is only proposing another solution to the CP problem, albeit it involves only reducing the impact of the value of $\theta$ on the value of $d_n$, and thus proposing another explanation to why $d_n$ is so small. So he is not "removing" the CP problem, he is just (attempting to) solve it.
Note 2: There are other physical implications of the theta term, like a $\theta$-dependent vacuum energy (see Vafa-Witten theorem), but I am not sure whether they can be experimentally tested. Maybe someone else can add on this.