Using a PRP $\pi: \{0,1\}^{16} \to \{0,1\}^{16}$ to construct an ideal cipher
There are $2^{16}!$ distinct permutations of the 16-bit strings $\{0,1\}^{16}$.  For any fixed Feistel structure built out of one of these as you suggest, there are still only $2^{16}!$ possible outcomes.

There are $2^{128}!$ distinct permutations of the 128-bit strings $\{0,1\}^{128}$.  In an ideal cipher, for any fixed key $k$, $E_k$ is an independent uniform random permutation: each possible permutation has probability $1/2^{128}!$ of being $E_k$.

But in your construction, there are at least $2^{128}! - 2^{16}!$ permutations that $E_k$ cannot be.  (There may be more because conceivably some pairs of permutations may collide under the Feistel structure, pending further analysis to rule that out.)  So no matter what Feistel structure you choose, or non-Feistel composition of the permutation, you cannot get an ideal 128-bit block cipher out of a random 16-bit permutation.

What about a pseudorandom permutation family?  Maybe you can, on average, make a good PRP out of this, if you specified enough details to matter.

Table lookups are, indeed, a common design element in cryptographic primitives, including the venerable DES.  You can view AES as a composition of table lookups and xor, but as the rest of the paper demonstrates this implementation strategy will lead you into trouble, which is why alternative designs like Serpent and newer designs like Salsa20 don't even tempt implementors into using secret-dependent table lookups.

Further, to make a thing that can be computed with, rather than a probability distribution that can be studied, you need to choose particular tables—and as Don Coppersmith and his team at IBM learned in 1974, the choice of tables can be tricky.