While having the magic one button solution is enticing the old manual approach can give more control using basic modelling techniques.
Start by removing the unwanted edges.
See how many vertices you need - you can optionally add corner edges to clarify the targets. In this example I need to add three more vertices to each edge.
Use CtrlR to add more edge loops - use the mouse scroll wheel or + and - on the numpad to change the number of cuts being added.
Select all the vertices in two edge loops to be filled in.
Choose Grid Fill (2.69 or higher) - this is available in File->Faces->Grid Fill or search after pressing space.
For versions before 2.69 you can use Bridge Edge Loops - File->Edges->Bridge Edge Loops or search after pressing space. This is still available in 2.69. You may find this works better in edge select mode without any corner connecting edges being selected, while grid fill works better if you have the corner edges in place.
The grid fill initially uses the order the vertices are selected to fill in the faces, if you initially get a strange fill you may want to press F6 (also available at the bottom of the toolbar T) to adjust the Offset until it fills in nicely.
You can also adjust how the bridge edge loops works
Repeat for each side. This gives you a nice final topology
You can also adjust this along the way by adding lop cuts between the two edges. The bridge edges has the option to do this for you and the grid fill will join these edges when you fill in the last two sides.
If you want the same result on the opposite side, if both are the same, you can select the top vertices and duplicate them, move to the opposite side using snap to vertex to align them and remove doubles to join together.