Is a "complete" cipher possible? Is a "complete" symmetric cipher possible?  By this I mean a symmetric cipher that is provably secure under the assumption that a secure symmetric cipher exists.
Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., these lecture notes). From this one-way function you can then construct symmetric-key encryption primitives (pseudorandom generators, block ciphers, CPA/CCA-secure encryption) using standard theoretical constructions.

One-way function $\to$ pseudorandom generator:


  Håstad, J., Impagliazzo, R., Levin, L.A. and Luby, M., 1999. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4), pp.1364-1396.


Pseudorandom generator $\to$ pseudorandom function:


  Goldreich, O., Goldwasser, S. and Micali, S., 1986. How to construct random functions. Journal of the ACM (JACM), 33(4), pp.792-807.


Pseudorandom generator $\to$ block cipher / pseudorandom permutation:


  Luby, M. and Rackoff, C., 1988. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), pp.373-386.


Block cipher $\to$ CCA-secure encryption:


  CBC mode + CBC-MAC