Typically PCB editors have a "replace" function:
Create the new footprint and put it into the PCB library. Update the component in the schematic. Go to layout. You should see a rats nest where the old component was. You need to redo only the broken traces.
Alternatively you may add the new component directly in the layout on top of the old component, so you wont break the traces already routed. Make new connections from the old traces to the new component (I assume the new fooprint differs in size only, not in pinout, so traces will not cross). Then remove the old component, clean up the PCB and back-annotate the schematic to reflect your changes.
Note this is a generic method, not specific to Altium - I wouldn't know what the specific commands are in Altium.