Jalapeño, 8 bytes

‥1r}⇅cₓ}u

Explained

      # Implicit opening brackets
‥1    # All numbers from input0 to 1
r}    # Repeated input1 times (To allow for repeat digits
⇅     # Then sorted, so it doesn't provide mirrors of the same set
cₓ}   # All choices of length Input1
u     # Unique elements only

Hex-Dump of Bytecode

       0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
0000: 2e 31 f9 c5 e2 e8 c5 e4                         

Try it Online!

APL(NARS), 22 chars

a/⍨∧/¨2≤/¨a←,¯1+⍳↑⍴/⌽⎕

Generate all combinations, and choose the ones that have elements <= 2 to 2. Possible I have not understood well I had seen only the example... test:

  a/⍨∧/¨2≤/¨a←,¯1+⍳↑⍴/⌽⎕
⎕:
  4 2
0 0  0 1  0 2  0 3  1 1  1 2  1 3  2 2  2 3  3 3 
  a/⍨∧/¨2≤/¨a←,¯1+⍳↑⍴/⌽⎕
⎕:
  4 3
0 0 0  0 0 1  0 0 2  0 0 3  0 1 1  0 1 2  0 1 3  0 2 2  0 2 3  0 3 3  1 1 1  1 1 2  1 1 3  1 2 2  1 2 3  1 3 3  2 2 2  2 2 3  2 3 3  3 3 3 

JavaScript (Firefox 30-57), 71 bytes

f=(n,k)=>k?[for(m of Array(n).keys())for(a of f(m+1,k-1))[...a,m]]:[[]]

I get to use keys() for once.

Clojure, 94 bytes

(defn f[k n](if(= 1 k)(for[i(range n)][i])(sort(set(for[i(f(dec k)n)j(range n)](conj i j))))))

Note the changed parameter order: 1st is k and 2nd is n. This saved 1 byte in (f(dec k)n).

J, 18 bytes

[:~.#~<@/:~@#:i.@^

Similar approach used in @Adám's solution.

Another approach using Cartesian product { for 24 bytes. Takes k on the LHS and n on the RHS.

~.@:(/:~&.>)@,@{@(#<@i.)

Usage

   f =: [:~.#~<@/:~@#:i.@^
   4 f 2
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│1 1│1 2│1 3│2 2│2 3│3 3│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Explanation

[:~.#~<@/:~@#:i.@^ Input: n on LHS and k on RHS
                 ^ Compute n^k
              i.@  Create a range [0, 1, ... n^k-1]
    #~             Create k copies on n
            #:     On each value in the range above, convert each digit to base-n
                   and take the last k digits of it
        /:~@       For each array of digits, sort it in ascending order
      <@           Box each array of digits
[:~.               Take the distinct values in the array of boxes and return it

MATL, 11 bytes

(There's a 9-byte solution based on Cartesian power, but Peter Taylor already did that. Let's try something different).

Combinations with replacement can be reduced to combinations without replacement as follows. We want n Cr k, for example with n=3, k=2:

0 0
0 1
0 2
1 1
1 2
2 2

We can compute n+k-1 C k:

0 1
0 2
0 3
1 2
1 3
2 3

and then subtract 0 1 ... k-1 from each row:

+q:2GXn2G:-

Explanation:

+q     % take two inputs n, k and compute n+k-1
:      % range [1,2...,n+k-1]
2G     % push second input, k
Xn     % combinations without replacement
2G:    % range [1,2,...,k]
-      % subtract with broadcast. Display

The code works in release 13.1.0 of the language/compiler, which is earlier than the challenge.

You can try it online! Note that the online compiler has been updated to release 14.0.0, so Xn needs to be changed to XN.

Dyalog APL, 22 bytes

{∪{⍵[⍋⍵]}¨↓⍉⍺⊥⍣¯1⍳⍺*⍵}

Requires ⎕IO←0, which is default in many APL systems. Takes k as left argument, n as right argument.

⍳⍺*⍵ 0 1 2 ... kⁿ
⍺⊥⍣¯1 convert to base k
⍉ transpose
↓ make matrix into list of lists
{⍵[⍋⍵]}¨ sort each...
∪ the unique

Python 3, 81 80

Recursive solution:

t=lambda n,k,b=0:[[]]if k<=0 else [[i]+l for i in range(b,n)for l in t(n,k-1,i)]

The function t(n, k, b) returns the list of all k-element multi-subsets of the range from b to n. This list is empty if k <= 0. Otherwise, we break the problem down based on the smallest element of the multi-subset, which we denote by i.

For each i in the range from b to n, we generate all of the k-multi-subsets with smallest element i by starting with [i] and then appending each (k-1)-multi-subset of the range from i to n, which we obtain by recursively calling t(n, k-1, i).

Mathematica, 31 29 bytes

Thanks to A Simmons for saving 2 bytes.

{}⋃Sort/@Range@#~Tuples~#2&

An unnamed function taking n and k as integer arguments in that order and returning a list of lists. The elements will be 1 to n. Works the same as Peter's CJam answer.

Python, 63 bytes

f=lambda n,k:n*k and[l+[n]for l in f(n,k-1)]+f(n-1,k)or[[]][k:]

A recursive method. To make a multiset of k elements, 1 to n, we choose to either:

• Include another instance of n, and it remains to make a multiset of k-1 elements from 1 to n
• Don't include another instance of n, and it remains to make a multiset of k elements from to 1 to n-1

We terminate when either k or n reaches 0, and if it k reached 0, we give a base case of the empty list. If not, we have the wrong number of elements, and so give the empty list.

Mathematica, 36 bytes

{##}&~Array~Table@##~Flatten~(#2-1)&

Please tell me there's a 1/6 bonus for using no []s...Or maybe for the many uses of ##?

Ruby, 56 55 bytes

Two solutions, surprisingly both the same length:

->n,k{[*1..n].repeated_permutation(k).map(&:sort).uniq}
->n,k{(a=[*1..n]).product(*[a]*(k-1)).map(&:sort).uniq}

Hey, you did say we could use permutation builtins...

This simply generates all repeated permutations (the second one generates repeated Cartesian products) and removes ones that aren't in sorted order.

Thanks to Martin for saving a byte with 0...n -> 1..n!

Pyth, 7 bytes

{SM^UQE

Uses the same algorithm as Peter's answer.

    UQ   range(input())
      E  input()
   ^     repeated Cartesian product of ^^, ^ times
 SM      map(sort)
{        uniq

Jelly, 4 bytes

Thanks to Sp3000 for saving 2 bytes.

ṗṢ€Q

Input is n and k as command-line arguments in that order. Uses elements 1 to n.

Try it online!

Explanation

ṗ     # Get k-th Cartesion power of n.
 Ṣ€   # Sort each tuple.
   Q  # Remove duplicates.

CJam (8 bytes)

{m*:$_&}

Online demo

Dissection

{    e# Declare block (anonymous function); parameters are n k
  m* e# Cartesian product, which implicitly lifts n to [0 1 ... n-1]
  :$ e# Sort each element of the Cartesian product, to give them canonical forms
  _& e# Deduplicate
}