Let's say you have an $n$-digit number with $a$ $1$'s, $b$ $3$'s, $c$ $7$'s and $d$ $9$'s. The number of permutations is $n!/(a! b! c! d!)$.
Heuristically, unless there is a good reason for these not to be prime (e.g. if they are all divisible by $3$) each has probability on the order of $1/n$ of being prime.
If the number of permutations is much larger than $n$, it is very likely
that at least one of those is prime. For example, if there is one $1$, one $3$ and the rest are $7$, the number of permutations is $n!/(1! 1! (n-2)! 0!) = n(n-1)$ which is much larger than $n$ if $n$ is large. So I wouldn't be surprised if your conjecture is true; or if it is false, there is some
fairly small example.
I don't understand your idea to "find the biggest prime number". Of course there is no "biggest prime number", but apart from that,
even if we accept that there is some prime consisting of one $1$, one $3$ and, say, $10^6$ $7$'s, if we don't know which of the permutations it is we're not done. We'd still have to check a bunch of possibilities until we find one that's prime.
The bijective argument for all $p$ is the following. Write $n = ap + b$ where $0 \le b \le p-1$, so that $a = \lfloor \frac{n}{p} \rfloor$. Divide the set $[n] = \{ 1, 2, \dots n \}$ into $a$ groups of $p$ elements and $b$ elements left over. Consider the action of the cyclic group $C_p$ on the set of $p$-element subsets of $n$ by cyclic permutation on each of the $a$ groups of $p$ elements. There are two kinds of orbits, orbits of size $p$ and fixed points, so ${n \choose p}$ is congruent $\bmod p$ to the number of fixed points. And the fixed points are exactly given by the $a$ groups of $p$ elements themselves, of which there are $a = \lfloor \frac{n}{p} \rfloor$.
A generalization of this argument proves that
$${ap + b \choose cp + d} \equiv {a \choose c} {b \choose d} \bmod p$$
and iterating this identity proves Lucas' theorem
$${\sum a_i p^i \choose \sum b_i p^i} \equiv \prod {a_i \choose b_i} \bmod p$$
where $a_i, b_i$ are digits in base $p$; this can also be proven directly with a similar argument. You can see several other arguments like this at this blog post, including a bijective proof of Fermat's little theorem and Wilson's theorem.
An important corollary of this result is that if $p^k$ is the largest power of $p$ dividing $n$ then ${n \choose p^k}$ is not divisible by $p$ (which also follows from Kummer's theorem). This fact can famously be used to prove the first Sylow theorem.
Edit: Stripping out the group theory, here is the argument specialized to the case $p = 3$ for concreteness but there's nothing special about $3$ here. Write $n = 3a + b$ where $0 \le b \le 2$. Divide the set $[n] = \{ 1, 2, \dots 3a + b \}$ into $a$ groups of $3$ elements
$$\{ 1, 2, 3 \}, \{ 4, 5, 6\}, \dots \{3a-2, 3a-1, 3a \}$$
together with $b$ leftover elements $\{ 3a+1, \dots 3a+b \}$. Now we are going to group together the $3$-element subsets of $\{ 1, 2, \dots 3a+b \}$ as follows:
- There are $a$ special $3$-element subsets given by the groups $\{ 1, 2, 3 \}, \{ 4, 5, 6 \}$, etc. we just picked.
- All of the other $3$-element subsets can be organized into groups of $3$ as follows. Consider the function $f : [n] \to [n]$ which "rotates" each of the $3$-element sets by adding $1 \bmod 3$ to each of them; that is, $f(1) = 2, f(2) = 3, f(3) = 1, f(4) = 5, f(5) = 6, f(6) = 4$, etc. $f$ does not do anything to the "remainder" $\{ 3a+1, \dots 3a+b \}$. Then every $3$-element subset $\{ i, j, k \}$ not of the above form is matched up with exactly two other $3$-element subsets $\{ f(i), f(j), f(k) \}, \{ f(f(i)), f(f(j)), f(f(k)) \}$ under the action of $f$. For example, $\{ 1, 2, 4 \}$ is matched up with $\{ 2, 3, 5 \}$ and $\{ 3, 1, 6 \}$. The $a$ special $3$-element subsets are exactly the subsets with the property that $\{ i, j, k \} = \{ f(i), f(j), f(k) \}$, so they don't get matched up with anything by $f$.
The general result, again stripped of any explicit references to group theory, is the following. Suppose $p$ is a prime, $X$ is a finite set, and $f : X \to X$ is a permutation such that $f^p(x) = x$ for all $x \in X$. Then $X$ splits up as the disjoint union of the fixed points of $f$ together with subsets of size $p$ of the form $\{ x, f(x), f^2(x), \dots f^{p-1}(x) \}$; in particular, $|X|$ is congruent to the number of fixed points of $f$, $\bmod p$.
Best Answer
Consider, instead, subsets of $\{0,1,\ldots,p-1\}$. There will be twice as many subsets; and twice as many whose sum is a multiple of $p$ because you have the option of including $0$ in any subset.
Take any subset except the empty set and the full set. Call it $S_0=\{x_1,\ldots,x_k\}$. Note that $1\le k\le p-1$. There are $p$ sets $S_i=\{i+x_1,\ldots,i+x_k\}$ formed by adding the number $i$ to each element, as $i$ ranges from $0$ to $p-1$. This adds $ki$ to the sum, so the sums are all different $\pmod p$ because we have excluded the empty set and the full set.
So the $2^p-2$ subsets split up into $p$ equal groups. There are $(2^p-2)/p$ that are multiples of $p$.
Add back in the empty set and full set to give $2+(2^p-2)/p$. Pair up sets that include $0$ with sets that don't, and remove the sets that include $0$. That leaves $1+(2^{p-1}-1)/p$. Lastly, remove the empty set to leave $(2^{p-1}-1)/p$.