Conceptual explanation for the sign in front of some binary operations
I find the question quite interesting (in the sense that similar questions related to sign factors appearing in various different algebraic structures with no apparent reason, have been going through my studies for quite some time in the past..)
Although i am not really familiar with most of your examples, since you are also mentioning associative and Lie algebras, i will refer to a similar "phenomenon" from graded algebras: This has to do with the $\mathbb{Z}_2$-graded tensor product, between two associative superalgebras ($\mathbb{Z}_2$-graded algebras) $A$ and $B$. If $b$, $c$ are homogeneous elements of $B$ and $A$ respectively, then the so-called super tensor product algebra or $\mathbb{Z}_2$-graded tensor product algebra, of superalgebras, is the superalgebra $A\underline{\otimes} B$, whose multiplication is given by
$$
(a \otimes b)(c \otimes d) = (-1)^{|b| \cdot |c|}ac \otimes bd
$$
with $|b|, |c|\in\mathbb{Z}_2$. Here the sign factor, reflects the braiding of the monoidal category of representations of the group hopf algebra $\mathbb{CZ}_2$: Recall that, superalgebras can be alternatively viewed as algebras in the the braided monoidal Category ${}_{\mathbb{CZ}_{2}}\mathcal{M}$ (i.e. the Category of $\mathbb{CZ}_{2}$-modules) and that the above multiplication can be abstractly written as:
$$
m_{A\underline{\otimes} B}=(m_{A} \otimes m_{B})(Id \otimes \psi_{B,A} \otimes Id): A \otimes B \otimes A \otimes B \longrightarrow A \otimes B
$$
Here, the braiding is given by the family of natural isomorphisms $\psi_{V,W}: V\otimes W \cong W\otimes V$ explicitly written:
$$
\psi_{V,W}(v\otimes w)=(-1)^{|v| \cdot |w|} w \otimes v
$$
where $V$, $W$ are any two $\mathbb{CZ}_2$ modules.
Furthermore, this braiding is induced by the non-trivial quasitriangular structure of the group Hopf algebra $\mathbb{CZ}_{2}$, given by the $R$-matrix:
\begin{equation}
R_{\mathbb{Z}_{2}} =\sum R_{\mathbb{Z}_{2}}^{(1)} \otimes R_{\mathbb{Z}_{2}}^{(2)}= \frac{1}{2}(1 \otimes 1 + 1 \otimes g + g \otimes 1 - g \otimes g)
\end{equation}
through the relation: $\psi_{V,W}(v \otimes w) = \sum (R_{\mathbb{Z}_{2}}^{(2)} \cdot w)
\otimes (R_{\mathbb{Z}_{2}}^{(1)} \cdot v)=(-1)^{|v| \cdot |w|} w \otimes v$.
For yet another point of view, the above mentioned $R$-matrix can be considered to be "generated" by the corresponding bicharacter (or: commutation factor) of the $\mathbb{Z}_2$ group.
There are bijections between $R$-matrices, braidings and bicharacters (which here are actually commutation factors) in the braided, graded setting for either assoc or Lie braided ("colored" is another name), graded algebras.
All these can be generalized for graded algebras, gradings and braidings, or $R$-matrices, or bicharacters of the corresponding groups, for any finite, abelian group. Also for $\mathbb{G}$-graded, $\theta$-colored Lie superalgebras, to produce more complicated bicharacters $\theta:\mathbb{G}\times\mathbb{G}\to k$ (which in the example above where $\mathbb{G}=\mathbb{Z}_2$ is exactly the sign factor of the $\mathbb{Z}_2$ abelian group).
To conlude: the sign factors here, are an "implicit" appearance of the corresponding group bicharacters. And they can also be viewed as braidings of the corresponding category of representations or as $R$-matrices for the corresponding quaitriangular group hopf algebras (of the fin, abelian, grading group).
If you are interested in these examples and you consider them relevant to your question, you can also take a look at the description in this answer: https://mathoverflow.net/a/261466/85967 and my linked paper therein.
As Gabriel C. Drummond-Co commented, it has to do with suspensions that are implicit. I'll do it with the example of Gerstenhaber and Voronov and the others should follow similarly. Let us denote $M_2(x,y)=x\cdot y$ the product that we want to define based on the brace $m\{x,y\}$. If we define it as a map $(s\mathcal{O})^{\otimes 2}\to s\mathcal{O}$ (suspension as graded vector spaces), then the natural thing to do is using the brace $m\{-,-\}:\mathcal{O}^{\otimes 2}\to \mathcal{O}$, but to do so one has to compose with suspensions and desuspensions. Namely, $M_2(x,y)=s(m\{(s^{-1}x,s^{-1}y)\})$. And it's applying $(s^{-1})^{\otimes 2}(x,y)$ what makes the sign $(-1)^{|x|}$ appear. If we use $(s^{\otimes 2})^{-1}$ instead then we get the original sign $(-1)^{|x|+1}$.