The answer is "yes". I am a little pressed for time right now, so I'm going to restrict myself to the case where $\Sigma$ is a disc. This will be a real pain to explain without pictures, so I suggest drawing what I am saying below.
The proof will be by induction on the number $n$ of vertices. The base case is $n=2$, where the result is trivial. Assume now that $n>2$. Consider two spines $s_1$ and $s_2$ on $\Sigma$ with $n$ leaves $p_1,\ldots,p_n$ (arranged cyclically around the circle). There are unique embedded edge paths $\rho$ and $\rho'$ in $s$ and $s'$ connecting $p_1$ to $p_2$. Perform your moves to $s$ and $s'$ such that the lengths of $\rho$ and $\rho'$ (i.e. the number of edges they contain) is as small as possible.
I claim that $\rho$ and $\rho'$ each have length $2$. Indeed, the path $\rho$ divides $\Sigma$ into two sub-discs. One of these (call it $D$) has boundary consisting of $\rho$ together with the arc from $p_1$ to $p_2$ on $\partial \Sigma$ that does not contain any other $p_i$'s. The key observation is that $D$ cannot contain any points of $s$ in its interior. If $\rho$ has more than two edges in it, you can perform one of your local moves on an interior edge and shrink $\rho$ (this shrinks $\rho$ since the portion of $\rho$ on your "local move" has to be on "one side" -- draw the picture!). A similar things holds for $\rho'$.
So now $\rho$ and $\rho'$ consist of two edges. Isotoping $s$ and $s'$, we can assume that in fact $\rho = \rho'$. Let $q$ be their common interior vertex. We can delete the two edges of $\rho$ from $s$ and collapse a small disc on the circle to get a new spine $\hat{s}$ on a disc with $(n-1)$ leaves $q,p_3,\ldots,p_n$. Similarly, we can delete the two edges of $\rho'$ from $s'$ and collapse a small disc on the circle to get a new spine $\hat{s}'$ on a disc with $(n-1)$ leaves $q,p_3,\ldots,p_n$. By induction, we can connect $\hat{s}$ and $\hat{s}'$ using your local moves. Putting $\rho$ and $\rho'$ back, we get a sequence of moves connecting $s$ and $s'$.
