Using only logical symbols and "+, $\cdot$, $0$, $1$ translate into first-order logic: $k \mod 4 = l\mod 3$
I have attempted to solve this and actually written down a solution but I am not sure if it is enough, namely, if I don't have to rule out the possibility that $r = 3 \lor r=4$ My solution: $$(\exists a,b,r)(k = (1+1+1+1)a + r \land l=(1+1+1)b+r)$$ This notation does not cater for scenarios, when - let's say - $r=4$, but the standard notation of a number does. Therefore, should I extend my answer?
Your solution is correct provided that you interpret "$k \bmod 4 = \ell \bmod 3$" to mean that there is an integer $r$ such that $k \equiv r \bmod 4$ and $\ell \equiv r \bmod 3$.
Another interpretation of "$k \bmod 4 = \ell \bmod 3$" is that the remainder when $k$ is divided by $4$ is equal to the remainder when $\ell$ is divided by $3$. Under this interpretation, the only possible remainders are $0$, $1$ and $2$, since, although $3$ is a remainder modulo $4$, it is not a remainder modulo $3$. So in this case, your solution would look like $$(\exists a,b,r) ( \cdots \wedge (r=0 \vee r=1 \vee r=1+1))$$ where $\cdots$ is the same as what you already have.