Bridge will work fine for this situation. But if bridge did fail that means both edges aren't actually open edges (or they share the same vertex, which is highly unlikely with this particular model). If they aren't open edges then just select the polygons that are there and bridge the polys instead of edge.
it seems the mighty Bridge could be of assistance, however, in that situation the most your going to get out of 4 edges is a tube! Tho you could use cap, to then get the top and bottom connected. Also there is create, which lets you create a polygon, can be useful in combination with vertex snap.