Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held A set of parties can securely generate a random number $r \in \{1,2,3,\dots, k\}$ when $k$ is publicly known. However, can we generate the random number $r$ if $k$ is not publicly known and is held by the parties using a VSS scheme? 

Can you point me to any Multiparty Computation literature which looks at the above question?
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.