find all paths from source to destinations and then calculate the path with minimum cost
One way to solve this is a Dijkstra variant with the following DP-Relaxation:
The distance array will be 2-dimensional array for which $Dist[i][j]$ is the shortest path from the source to the city $i$ using $j$ wildcards.
When processing a vertex $i$, for an incident edge $e\{i, j\}$ with cost $c$ we update as following:(for all values of k)
$Dist[j][k] = min(Dist[j][k], Dist[i][k] + C)$ 
$Dist[j][k] = min(Dist[j][k], Dist[i][k-1])$
The correctness follows from the fact that we are trying all placements of the wildcards and keeping the so-far-optimal.
The runtime is the usual Dijkstra runtime multiplied by the $K$ factor in the relaxation i.e. $O((e+n\log(n))k)$ using Fibonacci Heaps.