The values of B being in ascending order along a row has nothing to do with the randomization. It is because A is in order - because that is how nchoosek works. Does your actual use case involve the application of nchoosek to generate A? If no, your code should work.
In either case, I suspect you want to randomize the columns on a per-row basis, rather than an array-wide column permutation. For that, a loop would be pretty simple:
[nrow,ncol] = size(A);
C = B;
for irow = 1:nrow
colRand = randperm(ncol);
C(irow,:) = B(irow,colRand);
I'm not seeing a way to do it without a loop right off, but one probably exists. Sometimes the non-loop methods aren't worth the hassle - they can be obfuscated or complicated, and occasionally even slower.