FWIW, the following produces what you want in Vim and Evil alike:
1. Yank the string into the register "a". 2. Select the first column. 3. Press "c". 4. Paste from the register with "C-r a".
(Since the change operation copies the original column into the " register, we have to use another register.)
I had actually tried this before, but I didn't use the register, instead I used `"' in "C-r" and it didn't work. I thought using register and `"' should be the same because `"' is a register too. Because of your email I tried it again with `"' and still not work, I then followed exactly your steps and worked. I then tried it in Vim and got exactly the same results. But I really don't understand why regular register worked but `"' as register doesn't work. Thanks, York