The largest possible value of $k$ is $2^{10} - 10$. First note that there are $2^{10}$ possible combinations for the origins per kind of fish. We show that there are always at least 10 exceptions (combinations that cannot be obtained by a customer), and that there is a way to supply the stalls for which there are exactly 10 exceptions.

Let us number both the stalls and the kinds of fish from 1 up to 10. For stall $i$, define the sequence $a_i \in \{M, N\}^{10}$ as the sequence of origins of the 10 kinds of fish in this stall. Let $c_i$ be the complement of $a_i$, i.e. the sequence obtained from $a_i$ by replacing all $M$'s with $N$'s and vice versa. As every customer has bought a fish from stall $i$, no customer can have $c_i$ as his sequence of fish origins. If all $c_i$ ($1 \le i \le 10$) are distinct, then we have 10 exceptions.

Otherwise, two of the stalls, say $i$ and $j$, sell each kind of fish from the same origin, i.e. $a_i = a_j$, and therefore also $c_i = c_j$. Define the sequences $d_k$ with $1 \le k \le 10$ by changing in $c_i$ the origin of kind $k$ of fish. These are the sequences which have exactly one origin in common with $a_i$. If a customer would have had sequence $d_k$, then this customer therefore could only have bought a fish from one of stalls $i$ or $j$, but not both, contradicting the given that every customer bought exactly one fish from every stall. Therefore also in this case, there are at least 10 exceptions.

We now construct a market in which it is possible to buy $2^{10} - 10$ possible combinations of fish origins as in the problem. Suppose that stall $i$ sells fish from the North Sea, unless the fish is of kind $i$ (in which case the fish is from the Mediterranean Sea). Let $b \in \{M, N\}^{10}$ be a sequence of origins in which the number of $N$'s is not exactly 1. We show that we can buy 10 fish from 10 stalls in such a way that $b$ is the sequence of origins. Let $A$ be the set of indices $i$ for which $b_i = M$, and $B$ be the set of indices $i$ for which $b_i = N$. For $i \in A$, buy a fish of kind $i$ from stall $i$, so that we get a fish from the Mediterranean Sea. If $B$ is empty, then we are done. If not, then $B$ has at least two elements. Write $B = \{i_1, \dots, i_n\} \subset \{1, \dots, 10\}$. For $i_k \in B$, buy fish of kind $i_k$ from stall $i_{k+1}$, considering the indices modulo $n$. Since $n \ge 1$, we have $i_{k+1} \ne i_k$, so this fish is from the North Sea, as required. $\square$