The problem is NP-hard.
We show this by reducing vertex cover:
Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V'$?
We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows:
All columns, except for the first, correspond to an edge. They get a regex $0^*1(0|1)^*$.
All rows correspond to a vertex. They get a regex that allows to write either
Finally, the first column counts the size of the vertex cover. It gets a regex, that allows for at most $k$ ones.
The correspondence between solutions to the regex crossword and vertex covers should be obvious.
Find a vertex cover of size 2 for the following graph:
$V_A = 0^* \big| 10110$
$V_B = 0^* \big| 11101$
$V_C = 0^* \big| 10011$
$V_D = 0^* \big| 11000$
$Counter = 0^* \big| 0^*10^* \big| 0^*10^*10^*$
$E_1 = 0^*1(0|1)^*$
$E_2 = 0^*1(0|1)^*$
$E_3 = 0^*1(0|1)^*$
$E_4 = 0^*1(0|1)^*$
Lastly, you can set up the "crossword" so that $V_A$ through $V_D$ are the top regexes and $Counter$ and $E_1$ through $E_4$ are the left side regexes.
Solving this regex crossword give you a vertex cover of size 2 for nodes $V_A,V_B$ or $V_C,V_B$.
If we change k to be 1 and $Counter$ to be $0^* \big| 0^*10^*$ as another example, the regex crossword is impossible to solve because there is no vertex cover of size 1.