We conjecture that $W$ gravity can be interpreted as the gauge theory of $phi$ diffeomorphisms in the space of dimensionally-reduced $D=2+2$ $SU^*(infty)$ Yang-Mills instantons. These $phi$ diffeomorphisms preserve a volume-three form and are those which furnish the correspondence between the dimensionally-reduced Plebanski equation and the KP equation in $(1+2)$ dimensions. A supersymmetric extension furnishes super-$W$ gravity. The Super-Plebanski equation generates self-dual complexified super gravitational backgrounds (SDSG) in terms of the super-Plebanski second heavenly form. Since the latter equation yields $N=1~D=4~SDSG$ complexified backgrounds associated with the complexified-cotangent space of the Riemannian surface, $(T^*Sigma)^c$, required in the formulation of $SU^*(infty)$ complexified Self-Dual Yang-Mills theory, (SDYM ); it naturally follows that the recently constructed $D=2+2~N=4$ SDSYM theory- as the consistent background of the open $N=2$ superstring- can be embedded into the $N=1~SU^*(infty)$ complexified Self-Dual-Super-Yang-Mills (SDSYM) in $D=3+3$ dimensions. This is achieved after using a generalization of self-duality for $D>4$. We finally comment on the the plausible relationship between the geometry of $N=2$ strings and the moduli of $SU^*(infty)$ complexified SDSYM in $3+3$ dimensions.