You need to watch out for a couple landmines before embarking on this. Firstly, you need to avoid affirming the debt. When you affirm the debt it gives them grounds to restart the clock and if your negotiations fail, you don't want that. Secondly, you don't want to pay them until you have, in writing, a statement of what you're getting in consideration for paying. In other words, if you call your creditor and say "I will pay in full if you remove this from my credit report" and they say "ok great we'll certainly do that, I can take payment over the phone". Stop right there. Six months after this happens you don't want to find out that the person you spoke to thought you meant marking the debt as paid as opposed to fully removing it. You need to demand that they give you written notice that they will be removing the collection record from ALL of your credit reports and that the debt will be fully settled.
As a side note, you can start negotiations by offering a lower amount than full. For example you might say something like "I see on my credit report that you've listed this collection account against me. I can not affirm that that debt is valid but if you agree to take 50% and remove the record from my credit report". From here they could say anything but at least you've given yourself room to negotiate.
To get back to your original question. The impact to your score will probably be pretty big if you are successful in having all of your collection accounts removed. Creditkarma will provide you with a free FAKO score and can give you what your score would be if you do certain things (like pay off collections accounts).
As far as how fast the score will be updated, it'll be updated as fast as the collector removes your account. I'm guessing the process would take around a month. I'm basing that on how long it takes to do a credit report dispute. It could be less time if all your creditors do their reporting very quickly. It could be more if they don't do what they're supposed to and you have to do a dispute.