Não entendi a lógica usada para preencher a matriz, mas enfim, acredito que deveria ser algo assim:

linhas = int(input("Quantas linhas você deseja adicionar? "))
colunas = int(input("Quantas colunas você deseja adicionar? "))

matriz = []
for i in range(linhas):
    linha = []
    for j in range(colunas):
        linha.append(int(input(f'Digite o elemento da linha {i}, coluna {j}: ')))
    matriz.append(linha)

Ou seja, vai adicionando os números conforme vai lendo, sem precisar guardá-los na lista primeiros_numeros, que não achei necessária. Também não entendi para que serve o NumMar, então removi.

Outra opção é usar list comprehension:

linhas = int(input("Quantas linhas você deseja adicionar? "))
colunas = int(input("Quantas colunas você deseja adicionar? "))

matriz = []
for i in range(linhas):
    matriz.append([ int(input(f'Digite o elemento da linha {i}, coluna {j}: ')) for j in range(colunas) ])

Ou ainda:

linhas = int(input("Quantas linhas você deseja adicionar? "))
colunas = int(input("Quantas colunas você deseja adicionar? "))

matriz = [
  [ int(input(f'Digite o elemento da linha {i}, coluna {j}: ')) for j in range(colunas) ]
  for i in range(linhas)
]

E se quiser mostrar a matriz formatada, poderia alinhar os números, usando f-string (a partir do Python 3.6). Por exemplo:

for linha in matriz:
    print(' '.join(f'{n:3}' for n in linha))

Isso mostraria a matriz assim:

  1   2   3   4
  5   6   7   8
  9  10  11  12

No caso, {n:3} alinha o número à direita, ocupando 3 espaços. Consulte a documentação para mais informações.