You know the maximum possible digit sum (ignoring the prime condition for a moment) is $36$, due to the digitsum from $9999$ within your range.
The possible digitsums under that barrier that are divisible by $8$ (ignoring $0$) are $8, 16, 24, 32$.
How many ways can you write each of these as a sum of $4$ digits where each digit falls within $0 \leq d \leq 9$?
If you were working in a team and had to do this by hand, you could probably divide-and-conquer and have each person tackle a different digitsum in order to enumerate all the cases more quickly.
However, you already know the $24$ digitsum is a waste of time, since any number whose digitsum is divisible by $24$ will also be divisible by $3$, which means the number itself will be divisible by $3$ and therefore not prime.
Then you can eliminate the cases that can't possibly be rearranged to form a prime number (such as those missing a $1, 3, 7$, or $9$ to form the last digit of the prime).
This leaves you with the following cases:
$8 = [[0, 0, 1, 7], [0, 0, 3, 5], [0, 1, 1, 6], [0, 1, 2, 5], [0, 1, 3, 4], [0, 2, 3, 3], [1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3]]$
$16 = [[0, 0, 7, 9], [0, 1, 6, 9], [0, 1, 7, 8], [0, 2, 5, 9], [0, 2, 7, 7], [0, 3, 4, 9], [0, 3, 5, 8], [0, 3, 6, 7], [0, 4, 5, 7], [1, 1, 5, 9], [1, 1, 6, 8], [1, 1, 7, 7], [1, 2, 4, 9], [1, 2, 5, 8], [1, 2, 6, 7], [1, 3, 3, 9], [1, 3, 4, 8], [1, 3, 5, 7], [1, 3, 6, 6], [1, 4, 4, 7], [1, 4, 5, 6], [1, 5, 5, 5], [2, 2, 3, 9], [2, 2, 5, 7], [2, 3, 3, 8], [2, 3, 4, 7], [2, 3, 5, 6], [3, 3, 3, 7], [3, 3, 4, 6], [3, 3, 5, 5], [3, 4, 4, 5]]$
$32 = [[5, 9, 9, 9], [6, 8, 9, 9], [7, 7, 9, 9], [7, 8, 8, 9]]$
Then for each unique permutation of each case that falls within your acceptable range (also ending in $1, 3, 7$, or $9$), test if the number is actually prime. There are only $276$ numbers to test.
One way you can do this is by listing the (relevant) primes under $\sqrt{10000} = 100$:
$7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97$
Then you test each one for divisibility into your candidate number. If they all fail the test, then the candidate number is prime.
I assume you can at least use a calculator for this step, because otherwise this is probably too tedious a problem to do by hand. The size of your team would need to be large enough to be able to perform all the primality-check calculations in the time allotted.
Another approach (assuming you had a large enough team) is to divide the $1000-10000$ range up into chunks and have each person enumerate their section of the range and then use the segmented Sieve of Eratosthenes approach using the primes under $100$ to cross out the composite numbers. Then you can check the digitsums of the resulting primes directly.
Best Answer
If the sum of the digits of $n$ is $29$, then the number $n$ must be congruent to $2$ (modulo $9$). Since $29$ and $9$ are relatively prime, and their product is $261$, we need only consider numbers congruent to $29$ (modulo $261$). There are only about three dozen candidates between $1000$ and $9999$.
Furthermore, the average of the digits is $\frac{29}4>7$; no digit can be $1$, and only one digit can be below $6$. That means we can start our search at $2999$; the first candidate is $3161$, easily discarded, and we just repeatedly add $261$ until we get above $9999$.