This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph without loops -- see sections 3.1, 3.2 in the article.
To comment how the construction in the article differs from your question:
- I only needed a homomorphism to exist (with certain properties), not necessarily it to be surjective. On the other hand, the construction in the paper had enough of freedom to be able to be modified to a surjective one.
- The paper works with De Bruijn graph without loops. When loops are included, the condition simplifies even more: G is an image of a De Bruijn graph if and only if it is strongly connected, and contains a loop.
Whether a graph is strongly connected and has a loop is decidable in linear time. :-)