This sounds like a basic scaffolding approach. Map the reads using the contigs as your target and see how many read pairs map to different contigs. Those will indicate contigs that are ordered in a certain way. This will work if the contigs are no more than an insert size away from one another.

Probably there is a tool that can do this for you. Now that I wrote that you could alsor perhaps attempt to assemble you paired end reads, then once done assemble again the old contigs with the new ones.

We use ATLAS_GapFill for this task (as does the Broad, and others)

I have used SSPACE with success. It accepts multiple libraries (pair-end, mate-pair) and gave me quite good results. It also fills the gaps. For gap closing you can also try GapCloser from SOAPdenovo package.

Thanks for your answers! I will try all the suggestions!