Given a finite presentation $A^m\to A^n\to M\to 0$ of M, does it mean for any other presentation $\text{Ker}(f)\to A^k\xrightarrow[]{f} M\to 0$, the relations $\text{Ker}(f)$ is also finitely generated as $A$-module?
Equivalently, if the kernel of the surjective homomorphism $A^n\to M$ is finitely generated, is the kernel of any other surjective homomorphism $A^k\to M$ also finitely generated?
Note that similar result is true for finitely presented $A$-algebras as shown here. If it is not true, what is the obstruction here?
Yes, this is true (assuming you mean for $k$ to be finite). Much more generally, suppose you have any algebraic structure $X$ (in the sense of universal algebra) which is finitely presented, with generators $S$ and relations $R$. Then for any other finite generating set $T$ for $X$, there is a finite set relations on $T$ which suffice to give a presentation of $X$.
To find this finite set of relations, for each $s\in S$, choose a word $a_s$ on $T$ which is equal to $s$. For each $t\in T$, choose a word $b_t$ on $S$ which is equal to $t$, and let $c_t$ be the word on $T$ obtained by substituting $a_s$ for $s$ in $b_t$ for each $s\in S$. We then have a relation $c_t=t$ on $T$. In addition, for each relation in $R$, we get a relation on $T$ by substituting $a_s$ for $s$ everywhere in that relation.
I claim these finitely many relations on $T$ then give a presentation of $X$. Indeed, the relations $c_t=t$ imply that actually the elements $a_s$ generate the structure (since $c_t$ is built out of the $a_s$'s). Since these elements $a_s$ are also required to satisfy all the relations of $R$, this recovers the original presentation of $X$ by $S$ and $R$.