It seems you've already answered your own question. A* is likely the best approach. Yes of course it can be used in the way you describe, including using the height information to avoid mountains. As long as you're able to access information about any grid on the surface of your world, there's no reason you can't use it in the A* heuristic.
Finally, you're confusing path finding with path following at the end of your question. Path finding doesn't care about gravity, unless you add it as a heuristic and since you're on the surface of a planet, gravity will be essentially the same over the entire surface. Many games have gravity together with movement, I see no reason you can't.
Basically we want to map going from red to blue, to be the same on a sphere as it is on a cube.

Since A* is frequently getting neighbors to its current node, you can easily create a set of functions for getting adjacent nodes. For example, getXPlus()
, getXMinus()
, getZPlus()
and so on. These functions will take the current node and return the node in the direction specified by the function name.
Most of the time these functions can just increment a value and be done, however, on the edges, that will change.
You'll want to map the surface of your cube to a 2D coordinate system. However you do this is up to you, they don't have to line up, just give each grid space a unique X, Y coordinate.
Now when on an edge, and getting the adjacent grid space it's not necessarily going to be just incrementing the coordinates. We have to find out which face we're moving to and switch to the coordinates of that face.
For example, getting the XPlus coordinate here will change both the X and the Y coordinates because we're moving to a new grid space on a new face. The green line represents an edge between two faces.

Now these are just global coordinates, it may be easier to use an internal local coordinate system, with a 3rd dimension that represents the cube face you're currently on.
Either way, you need to have a unique coordinate for each grid space on the face of the cube. Traversing between them will depend on how you implement the coordinate system. You need to know where that coordinate maps to the surface of the sphere too.
All this should eventually be abstracted away so that you don't even know about it.