EDIT: the original argument was unnecessarily complicatedbelow assumes finite language, which I took for granted for no good reason.
$\DeclareMathOperator\Th{Th}\DeclareMathOperator\Diag{Diag}$ I believe the The class of countable substructures of $M$ does have the amalgamation property if the language of $M$ is finite.
First, ultrahomogeneity implies that for any $n$ there are only finitely many $n$-types realized in $M$, each of them principal (the type of any $n$-tuple is generated by the conjunction of its diagram). This implies that there are only finitely many nonequivalent formulas in $n$-variables (namely, disjunctions of the generators), hence $\Th(M)$ is $\omega$-categorical.\omega$-categorical by the Ryll-Nardzewski theorem. Alternatively, $\mathrm{Aut}(M)$ is oligomorphic as two $n$-tuples with the same diagram are in the same orbit, which is also equivalent to $\omega$-categoricity by (another variant of) the Ryll-Nardzewski theorem.
Then, take $A,B_i,f_i$ as aboveA,B_0,B_1\subseteq M$ and embeddings $f_i\colon A\to B_i$. Let $B_i^+$ be $B_i$ expanded with constants for every element $a\in A$ realized in $B_i^+$ by $f_i(a)$. Every finite subset of $T=\Th(M)\cup\Diag(B_0^+)\cup\Diag(B_1^+)$ is consistent because the class of finitely generated (= finite) substructures of $M$ has AP (or it is easily checked directly), hence there exists a countable model $C\models T$. Since $C\equiv M$, we may assume $C=M$ by categoricity, and then we can define $g_i\colon B_i\to C$ satisfying $g_0f_0=g_1f_1$ in the obvious way.

