Palatini identity sign

The sign is the paper is correct. I do not know where is the problem so i'm gonna give you some hints.

Using the fact that:

$$δΓ^{α}_{νμ} = cfrac{1}{2}g^{ασ}big(nabla_{ν}δg_{σμ} + nabla_{μ}δg_{νσ} - nabla_{σ}δg_{νμ}big)$$ $$δΓ^{α}_{αμ} = cfrac{1}{2}g^{ασ}big(nabla_{α}δg_{σμ} + nabla_{μ}δg_{ασ} - nabla_{σ}δg_{αμ}big) =cfrac{1}{2}g^{ασ}nabla_{μ}δg_{ασ} $$

and since:

$$g^{munu}δR_{munu} =left(nabla_{α}(δΓ^{α}_{νμ}) - nabla_{ν}(δΓ^{α}_{αμ})right)g^{μν}$$

after some manipulations we can see that:

$$Big(g_{μν}Box - nabla_{μ}nabla_{ν}Big)δg^{μν} = g^{μν}δR_{μν}$$

EDIT 1:

If you're talking about equation (3.8) in the paper, their calculation is correct. They vary with respect to the inverse metric. You vary with respect to the metric and in order to compare your result with theirs you'll need to use $g_{munu}g^{munu} = d Rightarrow delta g_{munu} g^{munu} = -delta g^{munu} g_{munu} $. Without performing the calculation, i suppose that the signs of all terms will be changed (your calculation is correct) and both variatons will lead to the same equations of motion.