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 -- see sections 3.1, 3.2 in the article.
Checking such conditions is clearly decidable in polynomial time, maybe even linear time (there I am not sure).