Sounds highly likely that Paula has problems. Might be worth changing the CIAs as well, as they may have been damaged the same time as Paula. They are also responsible for some floppy I/O.
The system will definately not boot without Paula, or the CIAs for that matter.
As for changing the PLCC device, personally I could do it blindfolded, but assuming you don't have access to SMD rework tools, a cheap alternative is to use a pyro pen. Get a butane powered soldering iron and remove the tip so you have a mini flame thrower :-)
I might add this is a bit tricky if you're not well experienced, and it's easy to put too much heat into the PCB and lift tracks. Practice on an old PCB first.
Hold the pyro pen approx 10cm away from the device and heat it in a continuous circular motion. Apply gentle upward pressure to one corner using a steel spike or screwdriver, and you'll find it'll suddenly lift off.
Use solder wick to remove all solder from the new IC and the PCB. Run a bead of solder paste over the pads on the PCB, position the IC correctly and gently heat it on until all the solder melts smooth and shiny. Check carefully for solder shorts and unsoldered pins. Wick off solder or apply more paste as required.
If you don't have solder paste, get some extremely fine solder (0.2mm or less) and a tiny soldering iron and hand solder it.
Hope that helps,
Anthony.
