Usando uma instrução case em uma restrição de verificação

Acho que você pode fazer o seguinte:

CREATE TABLE Grade
(
  salary_grade    char(1) NOT NULL CHECK (REGEXP_LIKE(salary_grade, '[A-G]', 'c')),
  salary_scale    char(2) DEFAULT 'S1' NOT NULL,
  CONSTRAINT pk_grade PRIMARY KEY (salary_grade),
  CONSTRAINT ck_grade_scale CHECK ( REGEXP_LIKE(salary_grade, '[A-D]', 'c') AND salary_scale = 'S1'
                                 OR REGEXP_LIKE(salary_grade, '[E-G]', 'c') AND salary_scale = 'S2' )
);

Consulte o esquema do SQL Fiddle aqui.

Você não precisa do UPPER() restrição em salary_grade já que a verificação de regex será suficiente (você já está verificando se é uma letra maiúscula entre A e G). Eu não acho que a restrição em salary_scale sozinho também é necessário, pois estaria contido, logicamente, na última restrição.

ATUALIZAÇÃO

Aqui está como você pode fazer isso com um CASE declaração:

CREATE TABLE Grade
(
  salary_grade    char(1) NOT NULL CHECK (REGEXP_LIKE(salary_grade, '[A-G]', 'c')),
  salary_scale    char(2) DEFAULT 'S1' NOT NULL,  
  CONSTRAINT pk_grade PRIMARY KEY (salary_grade),
  CONSTRAINT ck_grade_scale CHECK ( salary_scale = CASE WHEN REGEXP_LIKE(salary_grade, '[A-D]', 'c') THEN 'S1' ELSE 'S2' END )
);

Consulte o esquema do SQL Fiddle aqui.