A comment by D.W. makes a lot of sense (it would do in general but it does in this specific case since there are many different variants of the same problem). Hence, in my response I just refer to a few variants of the same problem (which contain descriptions of various algorithms):
Usually, the term $k$ shortest edge-disjoint paths is plainly interpreted as follows:
Given a graph $G$ and $k$ pairs of distinct vertices $(s_i, t_i)$, $1 \leq i \leq k$, find whether there exist $k$ pairwise disjoint shortest paths $P_i$, between $s_i$ and $t_i$ for all $1 \leq i \leq k$.
And this is taken from the paper you pointed to: Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics. Volume 85, Issue 2, pp 113--138. 1998.
This problem is known to be NP-hard for arbitrary values of $k$ but the authors actually provide a polynomial algorithm for the case of $k=2$ with positive edge-costs.
In this variant, there is no interest in minimizing any particular metric. The best result, to the best of my knowledge, refers to Directed Acyclic Graphs (DAGs) and $k=2$:
Torsten Tholey. Linear time algorithms for two disjoint paths problems on directed acyclic graphs. Theoretical Computer Science, 465:35–48, 2012
However, the oldest formulation I know of this problem actually considers the minimization of a specific metric:
Given a directed graph G containing $n$ vertices, one of which is a distinguished source $s$, and $m$ edges, each with a non-negative cost, find a pair of edge-disjoint paths from $s$ to $v$ of minimum total cost.
This problem is known to be a special case of minimum-cost network flow, and there is a brilliant, splendid, beautiful and amazing algorithm for solving it with $k=2$: Suurballe's algorithm.
Another variant that has received some attention imposes a limit on the number of edges (and these are known as Length Constraints):
Given a graph $G$ compute a pair of disjoint paths between nodes $s$ and $t$ of an undirected graph, each having at most $K$ edges.
Again, this problem is known to be NP-complete: Spyros Tragoudas and Yaakov L.Varol. Graph-Theoretic Concepts in Computer Science, volume 1197 of Lecture Notes in Computer Science, chapter Computing disjoint paths with length constraints, pages 357–389. Springer Verlag Heidelberg, 1997.
Approximation algorithms have been developed also for this particular variant. See: Longkun Guo. Frontiers in Algorithmics, volume 8497 of Lecture Notes in Computer Science, chapter Improved LP-rounding Ap- proximations for the k-Disjoint Restricted Shortest Paths Problem, pages 94–104. Springer International Publishing, 2014.
In all these works (but the first two ones), the authors refer to shortest paths but watch out what D.W. is asking in his comment: this is not to find the minimum number $m$ of shortest paths from which a set of $k$ shortest paths could be extracted such that they do not share any edge. In general, the computation of these $k$ shortest paths refer to an additional metric. For example, Tragoudas and Varol consider the minimization of the maximum length and Guo introduces the minimization of an additional parameter, $delay$.
Summarizing, there are many variants of the same problem, Suurballe's minimizes the sum of the cost of the pair of paths, others consider the minimization of the longest path (Tragoudas and Varol), and this is known as a min-max version but also max-min versions exist and this is just in case a metric is used. If not, it depends whether you impose limits or not on the length of the paths and other cases. All of them, however, are known to be exponentially hard.
I would like to end just by pointing out that I am not aware of any generalization of A$^*$-like search algorithms that deal with this problem. I think that can be definitely an interesting line of research.
Hope this helps,