I've been struggling for long with two similar problems and you are just referring to the combination of them: finding the best $K$ solutions and the Target-Value search problem. Since you are asking for algorithms, let me give you the best bib references I am aware of.
First, let me reformulate the second problem:
Given a graph $G(V,E)$ and a couple of vertices $s\in V$ and $t\in V$ find the simple path $P^*$ whose cost is as close as possible to a given value $k$, i.e., if $P_{s-t}$ denotes the set of all (simple) paths from $s$ to $t$ and $g(P)$ is the cost of a path which is defined as the sum of the cost of all of its edges, then $P^* = argmin_{\pi\in P_{s-t}} \{|c(\pi)-k|\}$
This problem is known as the Target-Value search problem and was originally introduced in Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleeer, Rong Zhou and Minh Do, Heuristic Search for Target-Value Path Problem. In case a path actually exists with a cost equal to $k$ then it simplifies to your problem. Note that while in the definition I said "simple paths" between parenthesis, the work cited above refers only to Directed Acyclic Graphs so that all paths are necessarily simple. Unfortunately, I am not aware of any generalization of this algorithm to Undirected (cyclic) graphs. An improvement over that paper was provided by much the same authors in Tim Schmidt, Lukas Kuhn, Bob Price, Johan de Kleer and Rong Zhou, A depth-first approach to target-value search
A different problem consists of computing the best $K$ solutions. This problem can not be solved with an A$^*$-like search algorithm because duplicate detection avoids re-expanding nodes while the second best solution might require going through the same node already considered in the best solution. One of the most influential works for this problem is David Eppstein, Finding the $k$ Shortest Paths. A recent contribution of the same problem is Husain Aljazzar, Stefan Leue, K$^*$: A heuristic search algorithm for finding the $k$ shortest paths
Now, how to combine these two problems is an unknown so that if you have any ideas ... :)