Just changing RandomChoice to RandomSample doesn't help, since RandomSample just means that none of the characters are repeated, and clearly you want to allow repeated characters, since one of your strings is "35UVUS". As far as I know, all you can do is oversample and remove duplicates. For example:

SeedRandom[1]
Take[
    DeleteDuplicates[rndnew[{10, 6}]],
    UpTo[5]
]

{"K1263G", "SXVXHC", "UO2PBL", "EC1FTJ", "0TKLEH"}

Just changing RandomChoice to RandomSample doesn't help, since RandomSample just means that none of the characters are repeated, and clearly you want to allow repeated characters, since one of your strings is "35UVUS". One idea is to oversample and remove duplicates. For example:

SeedRandom[1]
Take[
    DeleteDuplicates[rndnew[{10, 6}]],
    UpTo[5]
]

{"K1263G", "SXVXHC", "UO2PBL", "EC1FTJ", "0TKLEH"}

Another possibility is to index the possible random strings, and then do a random sample from the possible indices. For your case, the number of possible strings is simply 36^6. To convert from an index to a string:

characters = Join[CharacterRange["A","Z"], CharacterRange["0","9"]];

fromIndex[index_, len_] := StringJoin[
    characters[[1+IntegerDigits[index, 36, len]]]
]

Then, a function that returns n samples of length len strings:

sample[n_, len_] := fromIndex[#, len]& /@ RandomSample[1 ;; 36^len, n]

Example:

SeedRandom[1]
sample[5, 6]

{"0621O7", "0WH6XW", "ODLV4Z", "KWSN6U", "AMOSFA"}