Finding Minimum Weight Subgraph Spanning Tree
No, it's highly unlikely there is a polynomial time algorithm for this problem. The problem you describe is known as Steiner tree, and it is NP-hard. Moreover, it is computationally quite difficult from many other viewpoints as well.

A classical dynamic programming approach is the Dreyfus-Wagner algorithm running in $O^*(3^k)$ time, where $k$ is the number of terminals (i.e., the size of the set of pairs $S$ in your terminology). There is a lot of literature on the problem, so you might want to look at it from a particular viewpoint.