With constants, the answer to Q1 is "yes". Let me work on the natural numbers $\mathbf N = \{0,1,2,\dotsc\}$ for notational simplicity. The idea is to identify ${\bf N}$ with the shifted naturals $4 + \mathbf N$ using the shift function $f(n) := n+4$ and its partial inverse $g(n) := \max(n-4,0)$, and by using some pairing function $\pi: \mathbf N^2 \to \mathbf N$ that is inverted by coordinate functions $c_1, c_2: \mathbf N \to \mathbf 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
\begin{gather*}
0 \star n := f(n) \\
1 \star n := g(n) \\
2 \star n := c_1(n) \\
3 \star n := c_2(n)
\end{gather*}
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 $0$, then $(n \star n) \star (n \star n)$ is one, and if $n \star n$ is $1$, 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; 2 \star 5 := 11; 3 \star 5 := 12$$
then we have now made all the constants from $5$ to $12$ 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.), and also to constrain $2 \star 5$ and $3 \star 5$.
Now we need a pair of shift operators, say $f_1(n) := 2n+13$ and $g_1(n) := \max(\lfloor \frac{n-13}{2} \rfloor,0)$, and $f_2(n) := 2n+14$ and $g_2(n) := \max(\lfloor \frac{n-14}{2}\rfloor,0)$ to make room for all the constants that have been created. Note that $g_1,g_2$ invert $f_1,f_2$ respectively, and that $f_1,f_2$ have disjoint ranges. Encoding $g_1$ and $g_2$ is easy, e.g. we can enforce
$$ 5 \star n := g_1(n)$$
and
$$ 6 \star n := g_2(n)$$
for all $n$, as this does not conflict with the existing requirement that $5 \star 5 = 6 \star 6 = 0$. Encoding $f_1,f_2$ is slightly trickier. For $i=1,2$, we can write $f_i$ as a composition $f_i = h_i \circ k_i$, where $k_1: {\bf N} \to {\bf N}$ is an injective "Hilbert's hotel" map that maps $7$ to $0$ and avoids $8$ in the range, and $h_1: \mathbf N \to \mathbf N$ is such that $h_1(k_1(n)) = f_1(n)$ for all $n$, and $h_1(8)=0$; $k_2,h_2$ are defined similarly with $7,8,f_1$ replaced by $9,10,f_2$ respectively. Then we can enforce
\begin{gather*}
7 \star n := k_1(n) \\
8 \star n := h_1(n) \\
9 \star n := k_2(n) \\
10 \star n := h_2(n)
\end{gather*}
and $f_1(n)$ is then $f_1(n) = 8 \star ( 7 \star n )$, and similarly $f_2(n) = 10 \star (9 \star n)$.
Finally, we can encode pairing and coordinate functions as before:
\begin{gather*}
11 \star n := c_1(n) \\
12 \star n := c_2(n)
\end{gather*}
for $n \geq 13$, and also
$$ n \star m := \pi( g_1(n) + g_2(m), g_1(n) * g_2(m) )$$
for $n,m$ in the range of $f_1,f_2$ respectively (and in particular distinct), where we choose the pairing function $\pi$ to only take values $13$ and greater to avoid collision. Then we can recover addition and multiplication as before, e.g.
\begin{multline*}
n + m = 11 \star (f_1(n) \star f_2(m)) \\
= 11 \star ((8 \star (7 \star n)) \star (10 \star (9 \star n)))
\end{multline*}
and the constants $7,8,9,10,11$ expanded in terms of $2,3,4$, which can in turn be expanded in terms of $n$ by the previous identities.
