The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of
- a read-only input tape, surrounded by endmarkers,
- a finite state control,
- a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
- a stack
In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, and Computation (1st ed.) we find:
Theorem 14.1 The following are equivalent for $S(n)\geq\log n$.
- $L$ is accepted by a deterministic $S(n)$-AuxPDA
- $L$ is accepted by a nondeterministic $S(n)$-AuxPDA
- $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.
with the surprising:
Corollary $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.
The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.
Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking.
The above is a copy of large parts of an answer to another question. So in which sense does it answers the current question? It is not the smallest imaginable class that contains $\mathsf{CFL}$ and is closed under nondeterminism. But it is a very well known class (i.e. $\mathsf P$) and a natural machine model, which has been studied thoroughly in the past, and is still studied today (with an additional runtime restriction) in the context of LogCFL. Indeed, LogCFL is also closed under nondeterminism and is closer than $\mathsf P$ to $\mathsf{CFL}$, proving my point that the above (i.e. $\mathsf P$ = $\log n$-AuxPDA) is not the smallest imaginable class of this kind.