This is quite relevant to my article [Local Loop Lemma](https://link.springer.com/content/pdf/10.1007/s00012-020-0644-y.pdf).
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).