So for example:
How many permutations are there with 3 digits that add up to 4? For this question I just list all possible solutions:
004, 013, 022, 031, 040, 103, 112, 121, 130, 202, 211, 220, 301, 310, 400
but what if the number of digit (k) is really big or the sum (n) is big?
k=10, n=71 or k=8, n=62
I looked at some stars-and-bars problems but I feel like it is not applicable in this case. I really do not know what to do...
Allocating units to digits, it's straight stars-and-bars until $n$ reaches $10$ - there will be ${n+k-1 \choose n}$ options. Each digit position is a class, and increments are added to each, so you need to find the classification options.
For example in the $k=3, n=4$ that you worked in your question, the possibilities are ${6 \choose 4} = 15$ (happily matching the cases you found).
Another example, $k=5, n=8$ would have ${12 \choose 8} = 495$ options.
For $n \ge 10$, you have an added constraint of maximum $9$ units per digit so you would need to subtract these outcomes away from the simple formula above. Each time $n$ reached another multiple of $10$ the adjustment would become more complex to account for the potential for multiple digits breaking the $9$-limit simultaneously.
As a relatively simple example in this case, take $k=5, n=12$. Then the previous calculation gives ${16 \choose 12} = 1820$ options, but some of these would imply digit values greater than $9$ . To find this excess we can preallocate $10$ units to one digit position and recalculate how many of these constraint-breaking options we make with the remaining $2$ units: ${6 \choose 2}= 15$. So the answer here involves removing those options for each digit, $1820 - 5 \times 15 = 1745$ valid options.
Let us take the example of $k=8,n=63$, and see what we can do
Method I, generating functions
Each time, we generate $0\;thru\;9$ Let us write it as $(x^0 + x^1+ x^2 + .... +x^9)$
Then $(x^0 + x^1+ x^2 + .... +x^9)^8$ represents generating such numbers $8$ times,
and the coefficient of $x^{63}$ when we multiply it out will give the answer, $11,440$
Method II, stars and bars with inclusion-exclusion
We use the stars and bars method, and exclude "bad" results by deliberately allowing $10$ in one or more of the $8$ slots. Here it would lead to
$\binom{70}7 - \binom81\binom{60}7 + \binom82\binom{50}7 - \binom83\binom{40}7 + \binom84\binom{30}7 - \binom85\binom{20}7 +\binom86\binom{10}7 = 11,440$
Method III, stars and bars, attempting to eliminate inclusion-exclusion
Assume you have placed the maximum $9$ in each slot, (thus $72$ for $8$ slots),
now take out $72-63 = 9$ units, applying stars and bars.
We get $\binom{9+8-1}{8-1} = \binom{16}{7} = 11,440$
We may not be totally successful in eliminating inclusion-exclusion, e.g. in your example with $k = 8, n = 62$, we would have to use it on a minor scale, $\binom{17}7 - \binom81\binom77 = 19,440$
