AND means that all the criteria has to be met. Personally, I'd use one validation rule per field:
AND( ISPICKVAL(Status__c,"Support"), ISBLANK(Address__c))
AND( ISPICKVAL(Status__c,"Support"), ISBLANK(City__c))
AND( ISPICKVAL(Status__c,"Support"), ISPICKVAL(State__c,""))
The reason why is so that the correct field(s) will be highlighted for the user, so they can fix their mistakes.
As a single rule, however, you need to combine AND and OR to get the desired results:
AND( ISPICKVAL(Status__c,"Support"),
OR(ISBLANK(Address__c), ISBLANK(City__c), ISPICKVAL(State__c,"")))
This will cause the validation to trigger when any of the three fields are empty when Status is "Support."
If you'd like the checkbox or the Status picklist value to show the same error, you can combine the validation to a single formula:
AND( OR(MyCheckbox__c, ISPICKVAL(Status__c,"Support")), ISBLANK(Address__c))
Otherwise, if you want to show distinct errors, you'd just write additional validation rules:
AND( ISPICKVAL(Status__c,"Support"), ISBLANK(Address__c))
AND( MyCheckbox__c, ISBLANK(Address__c))
You can do the same thing for the other fields, as well.
IF(condition, true, false)
withcondition
.