Show us a (runable) snippet of code demonstrating your problem. Your first attempt at a replace should be fine so long as you are not using binmode output - Perl generally "Does The Right Thing"™. In particular, on input the OS's line sep turns into a character represented by \n and on output the character represented by \n is turned into the appropriate line sep for the system.

Note that, depending on the system, \n may not be a new line character. If you want to be sure you are getting a Windows CRLF pair then you need something like s/::::/\x{0D}\x{0A}/g;.

See perliol for more discussion of the Perl IO layers.