First of all, I really like the solution that Amber suggested and would recommend you use such a solution. If you create the SFDC Campaign from within the Marketo Program, it will automatically create the Campaign Membership Statuses in SFDC to align with the Program's Progression Statuses. If you prefer to create the SFDC Campaign in SFDC, you may want to create a "template" campaign that has the correct membership statuses: instead of creating a brand new campaign, you clone the existing Campaign, so you don't have to manually create the membership statuses every time.
And for the record: Marketo can read Custom Objects from SFDC, but cannot update Custom Objects, so it wouldn't work for your requirement.
Finally, you can use the "Add Task" flow step to create Tasks with status "Completed", which will show up in the activity history in SFDC for the affected Lead or Contact.
Best,
Jep