You’re not using the terms permutation and combination with their usual meanings. If I understand you correctly, you have $n$ kinds of object (e.g., the numbers $0,1,\dots,n-1$), and you want to form strings of $k$ of them, allowing repetitions and not requiring that every kind of object appear. (In your example, $n=4$ and $k=2$.) You want to count such strings in two ways.
(1) What you’re calling permutations: the order of the $k$ things matters. This is the case that Anthony Labarre answered: there are $n$ ways to choose the first object, $n$ ways to choose the second, and so on right down to the $k$-th and last object, so there are altogether $n^k$ such strings. If the objects are the numbers $0,1,\dots,n-1$, you’re counting the number of base $n$ integers that can be written with at most $k$ digits.
(2) What you’re calling combinations: all you care about now is how many of each kind of object appears in the string. In your example, for instance, $0111,1011,1101$, and $1110$ all have one $0$ and three $1$s, so they get counted as a single ‘combination’. Suppose that the objects are the numbers $0,1,\dots,n-1$. For $i=1,2,\dots,n-1$ let $k_i$ be the number of times $i$ occurs in a string; since each string has $k$ objects altogether, we must have $k_0 + k_1 + \dots + k_{n-1} = k$, where each $k_i$ is a non-negative integer. Conversely, any list $\langle k_0,k_1,\dots,k_{n-1} \rangle$ in which $k_0 + k_1 + \dots + k_{n-1} = k$ represents one possible ‘combination’. Thus, there are as many ‘combinations’ as there are solutions to the equation $k_0 + k_1 + \dots + k_{n-1} = k$ in non-negative integers. This is a standard problem; the answer is ${{n+k-1} \choose k}$. The discussions here and here may be useful.
We can represent a number with non-decreasing digits by placing vertical bars in a string of nine ones. The number of ones to the left of the vertical bar represents the digit. For instance,
$$| 1 1 1 | | 1 1 1 1 1 1 |$$
represents the number $0339$, while
$$1 1 | 1 1 | 1 1 | 1 1 | 1$$
represents the number $2468$. Since a particular number is determined by which four of the thirteen symbols (four vertical bars and nine ones) are vertical bars, the number of non-decreasing numbers with four digits (including leading zeros) is
$$\binom{13}{4} = \binom{13}{9}$$
as you found. To determine how many four-digit numbers (including those with leading zeros) are less than $5000$, we must subtract from these those non-decreasing four-digit numbers that are at least $5000$. Notice that in those non-decreasing four-digit numbers that are at least $5000$, the first vertical bar must be placed to the right of at least five ones. For instance,
$$1 1 1 1 1 | | 1 | 1 | 1 1$$
represents the number $5567$. Since a particular non-decreasing four-digit number that is at least $5000$ is determined by which four of the last eight symbols (four vertical bars and four ones) are vertical bars, the number of non-decreasing four-digit numbers that are at least $5000$ is
$$\binom{8}{4}$$
Hence, there are
$$\binom{13}{4} - \binom{8}{4}$$
non-decreasing four-digit numbers, including those with leading zeros, that are less than $5000$.
Alternate Method: A non-decreasing number is completely characterized by the number of times each digit appears. Let $x_k$ represent the number of times the digit $k$ appears in the non-decreasing four-digit number, including those with leading zeros. Since there are four digits,
$$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 4$$
A particular number is determined by which nine of the thirteen symbols (nine addition signs and four ones) is an addition sign. For instance,
$$1 + + + 1 1 + + + + + + 1$$
represents the number $0339$, while
$$+ + 1 + + 1 + + 1 + + 1 +$$
represents the number $2468$. Thus, the total number of non-decreasing four-digit numbers is the number of ways nine addition signs can be placed in a row of four ones, which is
$$\binom{4 + 9}{9} = \binom{13}{9}$$
From these, we subtract those non-decreasing four-digit numbers that are at least $5000$. The digits of non-decreasing four-digit numbers that are at least $5000$ satisfy the equation
$$x_5 + x_6 + x_7 + x_8 + x_9 = 4$$
A particular number is determined by which four of the eight symbols (four addition signs and four ones) is an addition sign. Hence, there are
$$\binom{4 + 4}{4} = \binom{8}{4}$$
non-decreasing four-digit numbers that are at least $5000$. Hence, the number of non-decreasing four-digit numbers that are less than $5000$, including those with leading zeros, is
$$\binom{13}{9} - \binom{8}{4}$$
Best Answer
Letting $i$ correspond to the first digit, $j$ to the second, $k$ to the third and $l$ to the fourth, the number of numbers is $$\sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k \sum_{i=0}^j 1$$ $$= \sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k \binom{j+1}{1}$$ $$= \sum_{l=0}^9 \sum_{k=0}^l \binom{k+2}{2}$$ $$= \sum_{l=0}^9 \binom{l+3}{3}$$ $$= \binom{9+4}{4} = 715$$