N=4 is SCFT, I don't think UV cut-off make sense in a SCTF. You need a cut-off when you renormalize a theory. Additionally, till now, plain old QCD has no gravity dual and I am 100% sure about that. Furthermore, again, not all CFTs have to admit a gravity dual although for many of them a gravity dual that does not originate from string/M-theory may be constructed (e.g. holographic massive gravity duals in CMT systems).
I don't think that people believe that the UV completion of a theory has a gravity dual. The theories that gauge/gravity duality is about are such that their strong coupling dynamics is in the IR not in the UV. People seek a UV completion of gravity but as far as QFT is concerned our main problem is the strongly coupled behavior of the IR dynamics (e.g. QCD).
As for the rest of your question it is vague and I am not sure what do you mean. You mean, can we construct a gravity dual in a $d+1$-dimensional bulk of some QFT which incorporates gravity in $d$-dimensions? If this is what you are asking the answer is no. There is no such example. Renormalization flow has been studied as a gradient flow in many examples (e.g. see Ioannis Bakas' work) and the question about locality again, its vague.
I know of some unpublished work where the gravitational theory in the bulk is an infinite dimensional derivative theory of (super)gravity which is non-local but UV complete. In principle this theory can be put in AdS background (see work by Anupam Mazumdar et. al.). And no, string theory does not seem to think gravity is holographic. String theory suggests that the CFT data are holographic.
Ok, this is a messed up answer motivated by a messed up question. Maybe you should take it one at a time ;)