I believe all these translations are in principle easy. The challenge is in implementing them cleanly and efficiently; the translations can be annoying and confusing.
As you describe, to go from a Heegaard splitting
to a triangulation, it's just a matter of a sequence of Pachner moves. If you allow (as is
usually sensible to do) non simplicial complex triangulations, where edges are allowed to form a loop in the manifold, then you can use one-vertex triangulations of the surfaces. There is only a finite set of these up to isomorphism, and the Pachner moves correspond to the one-skeleton for an equivariant cell division of Teichmuller space of the surface with a distinguished point (the vertex). For a finitely generated group, the translation from one set of generators to another has linear cost. The same principle works here, for any
fixed genus: it's a translation from generators for the mapping class group to
a set of generators to a mapping class groupoid generated by the Pachner moves. (Lee Mosher
in particular has studied this correspondence in detail). The linearity still holds,
or at least nearly holds (this depends on the details of definitions)
when you consider surfaces of every genus together, if you use Dehn twists
around a system of curves where each curve only meets a bounded number of other
curves (as is the usual convention).
If you allow ideal triangulations for the manifold minus some finite collection of curves, you can do even better: the number of simplices needed is linear in the number of powers
of Dehn twists using standard generators.
To go in the other direction, a triangulation is practically a special case of a Heegaard splitting: a regular neighborhood
of the 1-skeleton union its complement. If you want the handlebodies described in
standard form, it's essentially just a matter of choosing a spanning tree for the 1-skeleton and dual 1-skeleton, plus some method to give a homeomorphism from the regular neighborhood
of the spanning tree to a sphere with a set of distinugished points.
If a Heegaard diagram is described as a nonseparating system of g simple curves on the boundary of a genus g handlebody to which disks are attached in the complementary handlebody, this can be translated into a gluing map expressed as a word in Dehn twists in a reasonably straightforward way; this also gives a Dehn surgery description. In fact, Lickorish described a method in his paper showing that all 3-manifolds are obtained by Dehn surgery on links. I believe the number
of powers of Dehn twists needed should be a linear function of the number of bits used to describe the
$g$ curves using either traintracks or normal curve coordinates.