Is there a way to block specific picklist items by profile?

Try this - 

AND(
    CASE(
        CUSTOMER_STATUS__c,
        'Cancelled',               1,
        'Hold',                    1,
        'Hold - New Web Provider', 1,
        'Installation Aborted',    1,
        'Paused',                  1,
        'Partnership Compliance',  1,
        'Pending Cancellation',    1,
        0
    ) = 1,
    $Profile.Name <> "Performance Consultant",
    $Profile.Name <> "System Administrator"
)