I figured it out, there needs to be a "Null" condition to handle the case where the header is not present. The following policy will require SSE-KMS encryption on all objects in the bucket "testing".
{ "Version": "2012-10-17",
"Statement": [
{
"Effect": "Deny",
"Sid": "RequireAWSKMS",
"Principal": "*",
"Action": "s3:PutObject",
"Resource": "arn:aws:s3:::testing/*",
"Condition": {
"StringNotEquals": {
"s3:x-amz-server-side-encryption": "aws:kms"
}
}
},
{
"Effect": "Deny",
"Sid": "RequireEncHeader",
"Principal": "*",
"Action": "s3:PutObject",
"Resource": "arn:aws:s3:::testing/*",
"Condition": {
"Null": {
"s3:x-amz-server-side-encryption": "true"
}
}
}
]
}