Hi Naor, I think that you can achieve this with a SFDC worklow and field update, as I don't think you can use tokens on "previous value" in "data value change" triggers. you''ll have to save somewhere the previous account name in order to compare, this is probably one way:
First, create a custom field called "prior company name", this field will save the previous account name. then create a workflow on accounts that evaluated whenever a record is changed. the rule criteria should be "ISCHANGED(Name)", the field update rule will be the update of the custom field you created: PRIORVALUE(Name)
In Marketo, create a smart campaign with data value change
Hope that helps! If there's a simpler way, I'd be interested to hear also;)
Itay