Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held
You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to take enough randomness (security parameter number of bits more than the upper bound) and then compute the sum of the randomness held by each party modulo $k$ (plus 1). This can certainly be done via a circuit.