$\def\CC{\mathbb{C}}\def\cO{\mathcal{O}}$I will show that separating points and separating tangents is not enough for $M = \CC^2$. I will also make some general remarks afterwards.

Let $A \subset \cO(\CC^2)$ be those holomorphic functions $f$ such that $f(z,z^{-1})$ extends holomorphically to $z=0$. We observe:

$A$ is a subalgebra: This is obvious.

$A$ is closed: Proof We have $f \in A$ if and only if $\oint f(z,z^{-1}) z^n dz=0$ for all $n \geq 0$, where the integral is on a circle around $0$. This fact is preserved by uniform limits on compact sets. (Specifically, by uniform limits on that circle.)

$A$ separates points: Note that the functions $f(x,y) = x$, $g(x,y) = xy$ and $h(x,y) = y (xy-1)$ are all in $A$. The functions $f$ and $g$ alone separate $(x_1, y_1)$ and $(x_2, y_2)$ unless $x_1=x_2=0$. In that case, $h$ separates them.

$A$ separates tangent vectors: Again, $df$ and $dg$ are linearly independent at all points where $x \neq 0$, and $df$ and $dh$ are linearly independent at $x=0$.

$A \neq \cO(\CC^2)$ Clearly, $y \not \in A$.

Remarks We may as well replace $M$ by its holomorphic hull, so we can assume $M$ is Stein.

I thought about the inclusion $A \subset \cO(M)$ as a map $M \to \mathrm{Spec}(A)$. Of course, Spec isn't the right word in the analytic setting, and $A$ need not be finitely generated, but I decided to keep going anyway. Your hypothesis show that the map is an injective immersion, and my algebraic geometry intuition suggests that the image of $M$ should be dense, but you wanted $M = \mathrm{Spec}(A)$, and I saw no reason it couldn't be an open immersion instead.

I remembered this example from an old blog post of mine.

We could replace this specific example with any map $\phi$ from the punctured disc $D^{\ast}$ into $\CC^2$, asking for $f \circ \phi$ to extend to $D$. Since there are so many different $\phi$'s, and all of them appear to impose independent conditions, I am skeptical of a nice answer for $\dim M>1$.

On the other hand, I have a strong intuition that, if $\dim M \subseteq \CC$ and $H^1(M)$ is finite dimensional, the analogue of Runge's theorem holds. I'm thinking about a proof. I don't have a good intuition about (for example) $\CC$ minus a Cantor set.

$\def\CC{\mathbb{C}}\def\cO{\mathcal{O}}$

Here is a candidate counterexample for $M= \CC$: Is $e^{-z}$ in the closure of the algebra generated by $e^z$ and $e^{\sqrt{2}z}$? My current guess is "no", but I need to move on to actual work.

I will show that separating points and separating tangents is not enough for $M = \CC^2$.

Let $A \subset \cO(\CC^2)$ be those holomorphic functions $f$ such that $f(z,z^{-1})$ extends holomorphically to $z=0$. We observe:

$A$ is a subalgebra: This is obvious.

$A$ is closed: Proof We have $f \in A$ if and only if $\oint f(z,z^{-1}) z^n dz=0$ for all $n \geq 0$, where the integral is on a circle around $0$. This fact is preserved by uniform limits on compact sets. (Specifically, by uniform limits on that circle.)

$A$ separates points: Note that the functions $f(x,y) = x$, $g(x,y) = xy$ and $h(x,y) = y (xy-1)$ are all in $A$. The functions $f$ and $g$ alone separate $(x_1, y_1)$ and $(x_2, y_2)$ unless $x_1=x_2=0$. In that case, $h$ separates them.

$A$ separates tangent vectors: Again, $df$ and $dg$ are linearly independent at all points where $x \neq 0$, and $df$ and $dh$ are linearly independent at $x=0$.

$A \neq \cO(\CC^2)$ Clearly, $y \not \in A$.

I remembered this counterexample from an old blog post of mine.

Note that we could replace $z \mapsto (z, z^{-1})$ with any map $\phi$ from the punctured disc $D^{\ast}$ to $\CC^2$. There are many such $\phi$'s, and they all appear to impose independent conditions. This makes me pessimistic about any simple criterion for equality when $M = \CC^2$.