Find which bundles can be demanded together
This can be solved in polynomial time, by solving $2^{2m}$ linear programs.  (That might look exponential, but is polynomial in the size of the input, as the input size is $2^m$.)

Given a pair of bundles, you can check whether it is a demand-pair using linear programming; see below.  So, you can apply this to all candidate pairs.

Suppose we have two bundles, $X,Y$, and we want to know if they are a demand-pair.  Introduce a variable $p_x$ for each $x \in M$.  It's easy to write a linear equality that expresses that $X,Y$ have the same net-utility: $u(X)=u(Y)$.  Also, it's easy to write linear inequalities to express that no other bundle has higher net-utility: $u(X) \ge u(Z)$ for all other bundles $Z$.  Each of those is a linear (in)equality on the variables $p_x$.  We also have the inequalities $p_x \ge 0$.  Now use linear programming to test whether all of those inequalities are simultaneously satisfiable; if they are, there exists a price-vector where $X,Y$ are simultaneously demanded.

As an optimization, note that $X,Y$ are a demand-pair for market $M$ iff they are a demand-pair for market $X \cup Y$: without loss of generality you can set the price of every item in $(X \cup Y) \setminus M$ to $+\infty$.  Also, without loss of generality you can set the price of every item in $X \cap Y$ to 0.  Consequently, $X,Y$ is a demand-pair for market $M$ iff $X'=X \setminus Y$ and $Y'=Y \setminus X$ are a demand-pair for market $X' \cup Y'$.  This will make each linear program smaller and more efficient to solve.  It also means that you only need to test pairs that have no common intersection, so it suffices to test at most $3^m$ pairs $X',Y'$.