Eu consegui resolver o problema mudando o formato de UTF-8 para para Western(ISO 8859-1). Essa opção fica no canto inferior direito do vs code. Também tive que modificar o código, ele ficou assim:
#include <stdio.h>
#include <locale.h> // tive que incluir essa biblioteca
int main() {
setlocale(LC_ALL, "Portuguese"); // e esse comando também
printf("#########################################\n");
printf("Bem-vindo ao nosso jogo de adivinhação!\n");
printf("#########################################\n");}
