"0 should have the contents of your yank. It's a bit more tedious to type, but "0p should do what you want.
Alternatively, don't select-and-replace the old lines up front.  If you find those lines with a search, just hit n. over and over (after an initial p), then when they're all pasted, do ndd followed by as many n.s as necessary.
The biggest mental switch I've needed to make when moving to Vim is to figure out how to apply group edits sequentially.  I.e. rather than doing a bunch of edits on a line and then doing a bunch of the same edits on another line, I'll do the first edit on a bunch of lines (using . to great effect), then the second edit on a bunch of lines, etc.  Alternatively, the use of macros may help as they are fantastic, but sometimes a little more tedious to get working correctly with "complex" changes.