With constants, the answer to Q1 is "yes". Let me work on the natural numbers ${\bf N} = \{0,1,2,\ldots,\}$ for notational simplicity. The idea is to identify ${\bf N}$ with the shifted naturals $4 + {\bf N}$ using the shift function $f(n) := n+4$ and its partial inverse $g(n) := \hbox{max}(n-4,0)$, and by using some pairing function $\pi: {\bf N}^2 \to {\bf N}$ that is inverted by coordinate functions $c_1, c_2: {\bf N} \to {\bf N}$ (thus $(n,m) = (c_1(\pi(n,m)), c_2(\pi(n,m))$ for all $n,m$). The point is that the shift creates some "room" in which to store the unary functions. More precisely, define
$$0 \star n := f(n)$$
$$1 \star n := g(n)$$
$$2 \star n := c_1(n)$$
$$3 \star n := c_2(n)$$
for any n, and
$$n \star m := \pi( g(n) + g(m), g(n) * g(m) )$$
for $n,m \geq 4$. Then
$$ n + m = c_1( f(n) \star f(m) )$$
and
$$ n * m = c_2( f(n) \star f(m) )$$
and so one can write both multiplication and addition in terms of composition operations.
Clearly one can make the same idea work on the integers after placing them in one-to-one correspondence with the natural numbers (which distorts the addition and multiplication operations, but no actual properties of these operations were needed in the above construction).
I would imagine that some clever ad hoc trick would allow one to simulate constants such as 0,1,2,3, for instance by designing the $\star$ operation so that $n \star n$ is usually 0, though I don't see how to simulate four separate constants without using branching, which presumably is not allowed in this exercise.
UPDATE: OK, I found an ad hoc trick to encode constants, again working on the natural numbers for simplicity. The first observation is that one never wants to have a fixed point $n$ where $n \star n = n$, as then any binary operation formed by composition with $\star$ must always map this fixed point to itself. So we do the next best thing, which is to enforce
$$ n \star n := 0$$
for non-zero n, and
$$ 0 \star 0 := 1$$
(say). So $n \star n$ is always going to be either 0 or 1. Furthermore, if $n \star n$ is zero, then $(n \star n) \star (n \star n)$ is one, and if $n \star n$ is one, then $(n \star n) \star (n \star n)$ is zero. Hence if we then enforce
$$ 0 \star 1 = 1 \star 0 = 2$$
then we have the identity
$$ ((n \star n) \star (n \star n)) \star (n \star n) = 2$$
for all n, which allows us to define the constant 2 as a composition word from an arbitrary input n. If we then enforce
$$ 0 \star 2 = 1 \star 2 := 3$$
and
$$ 2 \star 0 = 2 \star 1 := 4$$
then we can define the constants 3 and 4 also, since $3 = (n \star n) \star 2$ and $4 = 2 \star (n \star n)$. If we then enforce
$$ 2 \star 3 := 5; 2 \star 4 := 6; 3 \star 2 := 7; 3 \star 4 := 8; 4 \star 2 := 9; 4 \star 3 := 10$$
then we have now made all the constants from 5 to 10 definable, with no constraints as yet as to how $\star$ acts on these constants, other than to annihilate the diagonal ($5 \star 5 = 0$, etc.).
Now we need shift operators, say $f(n) := n+11$ and $g(n) := \max(n-11,0)$, to make room for all the constants that have been created. Encoding $g$ is easy, e.g. we can enforce
$$ 5 \star n := g(n)$$
for all $n$, as this does not conflict with the existing requirement that $5 \star 5 = 0$. Encoding $f$ is slightly trickier. We can write $f$ as a composition $f = h \circ k$, where $k: {\bf N} \to {\bf N}$ is an injective "Hilbert's hotel" map that maps $6$ to $0$ and avoids $7$ in the range, and $h: {\bf N} \to {\bf N}$ is such that $h(g(n)) = n+11$ for all $n$, and $h(7)=0$. Then we can enforce
$$ 6 \star n := k(n)$$
$$ 7 \star n := h(n)$$
and $f(n)$ is then $f(n) = 7 \star ( 6 \star n )$.
Finally, we can encode pairing and coordinate functions as before:
$$ 8 \star n := c_1(n)$$
$$ 9 \star n := c_2(n)$$
$$ n \star m := \pi( g(n) + g(m), g(n) * g(m) )$$
for $n,m \geq 11$, where we choose the pairing function $\pi$ to only take values $11$ and greater to avoid collision. Then we can recover addition and multiplication as before.
