Yes, the problem is decidable. We give a (very slow) algorithm for checking if there exists a surjective homomorphism to $G$. This implies the result for genereal homomorphisms by checking all subgraphs of $G$.

It is easy to see that the following properties are necessary:

I There is a vertex in $G$ which is reachable from every other vertex using only 0-edges.

II There is a vertex in $G$ which is reachable from every other vertex using only 1-edges.

III $G$ is strongly connected.

However these conditions are not sufficient.

First note that when traversing the de Bruijn graph $B_n$, the current state will be forgotten after processing $n$ letters. In automaton language, $\delta(v, s) = \delta(u, s)$ for all vertices $u, v$ of $B_n$ and every word $s \in \Sigma^{\geq n}$. Let's call this property $n$-forgetful (I would imagine this has a name, but I cannot think of it).

Note that this property is very important, since we can reformulate the problem as does there exist a homomorphism from all left infinite strings to $V$ such that all strings with the same length $n$ suffix get sent to the same vertex, i.e. everything is forgotten after $n$ steps.

The $n$-forgetfulness property also implies that for any $s \in \Sigma^{\geq n}$ there must be paths starting at every vertex in $V$ and by following edges corresponding to the colours of $s$ all end up at the same vertex.

Now consider a graph $H = (V', A')$ where every vertex corresponds to a non-empty subset of $V$, i.e. $V' = \mathcal{P}(V) \setminus \emptyset$. We put an edge in colour $c$ from $u'$ to $v'$ if every vertex in $u'$ has an edge in colour $c$ to a vertex in $v'$. Now consider the following question:

Does there exist a subgraph of $H$ on the same set of vertices such that every vertex has exactly one outgoing edge in each colour such that all recurrent vertices correspond to single element subsets in $V$?

Note that this question is decidable (You can start with the single-vertex subsets and add other subsets one by one if they have a 0-edge and a 1-edge to existing subsets.) and needs to be answered positively for the forgetfulness property to hold.

Now suppose such a subgraph $H'$ exists. We pick a vertex satisfying (I) and call it $v_0$. Similarly we pick a vertex $v_1$ satisfying (II). Note that we can pick $H'$ such that $v_0$ is the unique sink of the subgraph obtained by taking all 0-edges from $H'$, while $v_1$ is the unique sink when taking all the 1-edges.

By considering the paths starting at the vertex $V \in V'$, we can observe that this corresponds to an algorithm forget the current state in $m$ steps, where $m$ can be chosen to be any number at least the length of the longest path to a single-vertex state. We want to use this algorithm to ensure $n$-forgetfulness. However, the problem is that if two strings become equal, they have to start this forgetting process at the same time.

To do this we to use properties which are sort of invariant under small translations such as minimizers/maximizers. In highly periodic strings minima/maxima are not really well defined, but then we can use periodicity instead.

We (re)start the forgetting algorithm (which decides where to go in $G$ during the next $m$ steps) if the length $9m$ suffix is the lexicographically greatest suffix of the length $10m$ suffix. Now as more letters are added at the information of the original state gets lost, unless we restart the algorithm within $m$ steps. This can have two causes:

the suffixes get greater and greater lexicographically: this cannot continue indefinitely, because there are only a finite number of possible suffixes, namely $2^{10m+1} - 1$.

the suffix is periodic with period smaller than $m$.

To take care of the periodic case we do the following to forget:

If the suffix of length $20m$ is periodic with period at most $m$, we consider the smallest period $p$. For every string $s$ of length $< m$ (up to cyclic permutation) which is not a power we check if there exists a cycle in $G$ corresponding to $s$ and if we can reach from all vertices using a path of the colours of $s^k$ (note that this is decidable). Let $K$ be the greatest necessary $k$. If the suffix of length $20m$ is periodic with smallest period at most $m$ we go to the corresponding cycle instead and do not start the forgetting algorithm.

Note that by picking $n \geq 2^{10m+1} \cdot 20m \cdot K$ we can ensure forgetfulness.

We still need to ensure that $f$ is surjective. We can do this by constructing a path starting at $v_0$ which visits all edges and taking its corresponding string $s$. Without loss of generality we can start it with a 1-edge. We call the length of this path $\ell$ and map all strings of the form $0^{n + 1 - i}s[0..i]$ according to this path. Thus we want to pick $m > \ell$.

Since we just care about the decision problem, it suffices to check conditions I, II, III and

IV $H$ has such a subgraph $H'$. (You can start with the single-vertex subsets and add other subsets one by one if they have a 0-edge and a 1-edge to existing subsets.)

V For every string of length at most $m$, there exists a cycle corresponding to that string and we can reach this cycle from any vertex using a power of the string.

1more comment