How do you create a large PRP from a small one? How can you efficiently create a pseudorandom permutation with a large domain given a PRP with a small domain? Meaning: given an $n$-bit PRP, how can I create an $n k$-bit PRP?

I'm only interested in security up to $C 2^{\frac{n}{2}}$ messages, when $C$ is a reasonably-sized constant. For a power-of-2 $k$, the Luby-Rackoff construction essentially achieves this, although it requires $k^2$ calls to the PRF.
The cascade construction extends a PRF (in particular, a PRP) with fixed input length to a PRF with an arbitrarily large input length.  If you want a PRP with large input length, you can use the Luby-Rackoff/Feistel transformation on the large-input PRF obtained from the cascade.

The cascade construction is analogous to the Merkle-Damgard paradigm for extending a fixed-input-length compression function to a hash function with arbitrary input length, except that cascade uses a secret-key primitive (the given PRP) in place of the compression function.  The secret keys for the small- and large-input PRFs are exactly the same size, and the number of invocations of the small-input PRF is the ratio of the input lengths (large divided by small).  Both of these efficiency measures are about the best one could hope for.

Let $F \colon \{0,1\}^k \times \{0,1\}^\ell \to \{0,1\}^k$ be the given PRF, where the first input denotes the "key," and denote $F_y(\cdot) = F(y,\cdot)$.  Note that the PRF output and key lengths must be equal.  If $F$ is a PRP, then $\ell=k$.

For a secret key $y \in \{0,1\}^k$ and an input $x = x_1 x_2 \cdots x_n$ where each $x_i$ is a block of length $k$ (the input length of the original PRF $F$), we compute the cascade iteratively as: $y_0 = y$, and $y_i = F_{y_{i-1}}(x_i)$ for $i=1,\ldots,n$; the final output is $y_n$. In words, the output on block $x_i$ becomes the key for the next invocation, on $x_{i+1}$.

Bellare, Canetti, and Krawczyk analyzed the cascade construction in
http://cseweb.ucsd.edu/~mihir/papers/cascade.html .  They proved that as long as the large inputs $x$ are encoded in a prefix-free manner (in particular, if all inputs have the same length), then the cascade construction yields a secure PRF.  Concrete bounds may be found in the paper.