FWIW, it seems likely to me there is a PTAS for the problem, following the basic idea in this paper. (This doesn't exactly answer your question, but I'll still describe the PTAS here in the answer section as it is too long to fit in a comment.)
Fix any constant $\epsilon>0$. Let $p$ be an an instance of the problem, i.e., a probability distribution on $[n]$.
Say that a code (a set of codewords) is $K$-fix-free if no codeword in the code that has length $K$ or less is a prefix or suffix of another codeword.
Fix $K=\lceil 1/\epsilon^2\rceil $. Compute a min-cost $K$-fix-free code for $p$, in time polynomial in $n$, as follows. For each of the (constantly many) subsets $S$ of strings of length at most $K$, consider the $K$-fix-free code $C(S)$ formed by assigning, to the $|S|$ largest probabilities in $p$, codewords from $S$ (matching smaller codewords to larger probabilities), then enumerating (in order of increasing length) the $n-|S|$ strings of length larger than $K$ that have no prefix or suffix in $S$, and assigning these $n-|S|$ strings as the codewords for the remaining $n-|S|$ probabilities (in order of decreasing probability). Each subset $S$ gives a code $C(S)$; take $C_0$ to be one of minimum cost (by enumerating all choices for $S$). $C_0$ is a minimum-cost $K$-fix-free code for $p$.
Note that the cost of $C_0$ is a lower bound on the cost of the optimal fix-free code for $p$, since the optimal fix-free code is also a $K$-fix-free code.
Next, convert $C_0$ into a fix-free code, without increasing its cost by more than a $(1+O(\epsilon))$ factor, as follows.
Within every codeword in $C_0$, insert an extra '1' into every (maximal) group of consecutive '1's of length $K' = \lceil 1/\epsilon \rceil$ or more. (This increases the cost by at most a $(1+\epsilon)$ factor, and the resulting code will still be $K$-fix free, and no maximal group of consecutive '1's in any codeword has length $K$.) Then, for every codeword in $C_0$ of length more than $K$, prepend $K'$ '1's followed by a '0', and append $K'$ '1's preceded by a '0'. (This modification uniquely marks the start and end of each codeword, making the code completely fix-free. The modification increases the cost by at most a $1+O(\epsilon)$ factor overall.) Take the resulting fix-free code $C_1$ as the solution.
Since $C_1$ costs at most $(1+O(\epsilon))$ times $C_0$, and the cost of $C_0$ is a lower bound on the cost of the optimal fix-free code, the fix-free code $C_1$ has cost at most $(1+O(\epsilon))$ times the cost of the optimal fix-free code.
