An integral cohomology operation related to Steenrod square?
From the Adem relations we get $Sq^1Sq^{k-1}=(k-2)Sq^k$. It follows that for $k$ odd we have $Sq^k=Sq^1Sq^{k-1}$. Note that we have $Sq^1=\rho\beta$, where $\rho$ is mod 2 reduction, so if $k$ is odd $\beta Sq^k=\beta Sq^1Sq^{k-1}=\beta\rho\beta Sq^{k-1}=0$ since $\beta\rho\simeq \ast$. Therefore we are forced to take $f$ such that $f\beta=0$. Working stably we would then get a map $g:H\mathbb{Z}\rightarrow\Sigma^{k}H\mathbb{Z}$ such that $2g=f$. That is $f$ is divisible by 2. Alternatively, any map $H\mathbb{Z}\rightarrow\Sigma^{k}H\mathbb{Z}$ that is divisible by two defines an $f$ with the requried properties. There are many such examples odd-primary torsion classes that work, as well as higher 2-torsion, although it is clear that they do not exist for every odd $k$.
For $k$ even $\beta Sq^k$ is nontrivial since $Sq^1Sq^k=Sq^{k+1}$. Therefore $f\beta=\beta Sq^k$ must be non-trivial as well but this cannot happen. Assume to the contrary that such an $f$ exists. Then we have that $Sq^kSq^1=Sq^k\rho\beta\in H^{k+1}(K(\mathbb{Z}_2,n-1);\mathbb{Z}_2)$ and $Sq^1Sq^kSq^1=Sq^{k+1}Sq^1\in H^{k+2}(K(\mathbb{Z}_2,n-1);\mathbb{Z}_2)$ are both non-trivial by Cartan. It follows that
$0\neq Sq^{k+1}Sq^1=Sq^1Sq^{k}=\rho\beta Sq^kSq^1=\rho f\beta Sq^1=0$
Since $\beta Sq^1=0$. This is a contradiction and so $f$ cannot exist when $k$ is even.
Such an $f$ only exists in two cases: when $k=1$ (when $\beta Sq^1 = 0$) and when $k=0$ (when $\beta Sq^0 = \beta$). Here is a proof, which will take a little work with the Steenrod algebra.
Let's suppose that $X$ and $Y$ are either $H\Bbb Z$ or $H\Bbb Z/2$ (not necessarily the same). Then the map $$ [X,Y]_t \to Hom_{A^*}(H^*Y, \Sigma^t H^*X), $$ sending a map to its (graded) effect on cohomology, is an isomorphism for $t \neq 0$. If one of $X$ or $Y$ is $H\Bbb Z/2$, it is an isomorphism for all $t$.
Let's prove this. This map is the edge morphism in the Adams spectral sequence $$ Ext_{A^*}^s(H^*Y, \Sigma^t H^*X) \Rightarrow ([X,Y]^\wedge_2)_{t-s} $$ and so it suffices to show that the Adams spectral sequence degenerates.
If $Y = H\Bbb Z/2$, then $H^* Y$ is free over $A^*$ and there are no higher Ext-groups.
If $Y = H\Bbb Z$, then $H^* Y = A^* / Sq^1$, which has a free resolution $$ \cdots \to A^* \xrightarrow{\cdot Sq^1}A^* \xrightarrow{\cdot Sq^1} A^* \to A^*/Sq^1 \to 0 $$ (using the basis of $A^*$ in terms of admissible monomials). Applying $Hom_{A^*}(-, \Sigma^* H^*(X))$ to this resolution, we get the chain complex $$ 0 \to \Sigma^* H^*(X) \xrightarrow{Sq^1 \cdot} \Sigma^* H^*(X) \xrightarrow{Sq^1 \cdot} \Sigma^* H^*(X) \to \cdots $$ which gives us the Ext-groups (in particular, we could interpret this as the Bockstein spectral sequence from mod-2 cohomology to integral cohomology). If $X = H\Bbb Z/2$, then the basis of admissible monomials shows that this is exact except in degree zero, where it recovers $ker(Sq^1 \cdot -) = Im(Sq^1 \cdot -)$. If $X = H\Bbb Z$, then $H^*(X)$ has a basis consisting of admissible monomials we similarly find that this is exact except in degree zero: $A^* / Sq^1$ is a direct sum of $\Bbb Z/2$ in degree zero with a bunch of free modules over $\Bbb Z/2[Sq^1] / (Sq^1 \cdot Sq^1)$ on the admissible monomials $Sq^{2k} Sq^{n_1} \cdots Sq^{n_r}$. Therefore, the higher Ext-groups vanish except for those contributing to $[X,Y]_0 = [H\Bbb Z, H\Bbb Z]_0$. The degree-zero part $Hom(A^*/Sq^1, A^*/Sq^1) = ker(Sq^1 \cdot -)$ has a basis consisting of $1$ and admissible monomials of the form $Sq^{2k+1} Sq^{n_1} \cdots Sq^{n_r}$.
In particular, we found in the course of the proof that the map $$ [H\Bbb Z, H\Bbb Z]_n \to [H\Bbb Z, H\Bbb Z/2]_n, $$ sending $f$ to $\rho_2 \circ f$, is injective for $n \neq 0$. The image is parametrized by those elements of $A^* / Sq^1$ which are sums of admissible monomials $Sq^{2k+1} Sq^{n_1} \cdots Sq^{n_r}$; this corresponds to the cohomology operation $\beta Sq^{2k} Sq^{n_1} \cdots Sq^{n_r} \rho_2$.
Thus:
The set $([H\Bbb Z, H\Bbb Z]_n)^\wedge_2$ is $2$-torsion for $n > 0$, and has a basis consisting of the cohomology operations $\beta Sq^{2k} Sq^{n_1} \cdots Sq^{n_r} \rho_2$ over $Sq^{2k} Sq^{n_1} \cdots Sq^{n_r}$ admissible monomials in the Steenrod algebra with $n_r > 1$.
The set $[H\Bbb Z/2, H\Bbb Z]_n$ has a basis of elements of the cohomology operations $\beta Sq^{2k} Sq^{n_1} \cdots Sq^{n_r}$ over $Sq^{2k} Sq^{n_1} \cdots Sq^{n_r} Sq^1$ admissible monomials in the Steenrod algebra.
The subset of elements of the form $f \beta$ are thus sums of elements of the form $$ \beta Sq^{2k} Sq^{n_1} \cdots Sq^{n_r} \rho_2 \beta= \beta Sq^{2k} Sq^{n_1} \cdots Sq^{n_r} Sq^1. $$ The image of right multiplication by $\beta$, therefore, has a basis consisting of sums of elements of the form $\beta Sq^{2k} Sq^{n_1} \cdots Sq^{n_r} Sq^1$, where $Sq^{2k} Sq^{n_1} \cdots Sq^{n_r} Sq^1$ is an admissible monomial in the Steenrod algebra. In particular, $\beta Sq^n$ is not of this form unless $n=1$ (when it is zero) or $n=0$ (when it is $\beta$).