Inclusion Criteria:

          -  Patients must sign the written informed consent form before any screening procedure.
             Informed consent must be documented before any trial-specific screening procedure is
             performed.

          -  Patients must be aged ≥18 years on the date of signing the informed consent.

          -  Patients must be willing and able to comply with scheduled visits, treatment schedule,
             laboratory tests, and other requirements of the trial.

          -  Patients who present histologically confirmed recurrent or metastatic HPV16+ HNSCC
             that is considered incurable by local therapies.

          -  Patients who have a tumor expressing PD-L1 [CPS ≥1] as determined by the Food and Drug
             Administration (FDA)-approved test PD-L1 22C3 pharmDx kit performed and evaluated
             according to the manufacturer's specifications.

          -  The eligible primary tumor locations are oropharynx, oral cavity, hypopharynx, and
             larynx. Patients may not have a primary tumor site of nasopharynx (any histology).

          -  Patients must not have had prior systemic anticancer therapy administered in the
             recurrent or metastatic setting. Systemic therapy which was completed more than 6
             months prior to randomization, if given as part of multimodal treatment for locally
             advanced disease is allowed.

          -  Patients who have measurable disease based on RECIST 1.1 as determined by the site and
             confirmed by BICR. Tumor lesions situated in a previously irradiated area are
             considered measurable, if progression has been demonstrated in such lesions disease by
             RECIST 1.1.

          -  Patients have Eastern Cooperative Oncology Group (ECOG) performance status ≤1.

          -  Patients have adequate bone marrow function.

          -  Patients have adequate hepatic function.

          -  Patients should have adequate kidney function, assessed by the estimated glomerular
             filtration rate ≥45 mL/min using the Chronic Kidney Disease Epidemiology Collaboration
             (CPK-EPI) equation.

          -  Patients should be stable with adequate coagulation.

          -  All patients must provide a tumor tissue sample (formalin fixed paraffin embedded
             (FFPE) blocks/slides) from archival tissue, or fresh biopsy if collected as part of
             patient's standard clinical practice before the first dose of trial treatment.

          -  Women of childbearing potential (WOCBP) must have a negative serum (beta-human
             chorionic gonadotropin) at screening. Patients that are postmenopausal or permanently
             sterilized can be considered as not having reproductive potential.

        Exclusion Criteria:

        Medical conditions:

          -  Patients are pregnant or breastfeeding.

          -  Patients present primary tumor site of nasopharynx (any histology).

          -  Patients with uncontrolled intercurrent illness, including but not limited to:

               1. Ongoing or active infection which requires systemic treatment with antibiotics or
                  corticoid therapy within 14 days before the first dose of trial treatment.

               2. Symptomatic congestive heart failure (Grade III or IV as classified by the New
                  York Heart Association), myocardial infarction within 3 months before screening,
                  unstable angina pectoris, or cardiac arrhythmia.

               3. Arterial thrombosis or pulmonary embolism within ≤6 months before the start of
                  trial treatment.

               4. Known recent history (in the past 5 years) or presence of significant pulmonary
                  conditions such as uncontrolled chronic lung disease, or any evidence of
                  interstitial lung disease, or active, non-infectious pneumonitis.

               5. Uncontrolled hypertension defined as systolic blood pressure ≥160 mmHg and/or
                  diastolic blood pressure ≥100 mmHg, despite optimal medical management.

               6. Known primary immunodeficiencies, either cellular (e.g., DiGeorge syndrome, T
                  negative severe combined immunodeficiency [SCID]) or combined T and B cell
                  immunodeficiencies (e.g., T and B negative SCID, Wiskott Aldrich syndrome, ataxia
                  telangiectasia, common variable immunodeficiency).

               7. Ongoing or recent evidence (within the past year) of significant autoimmune
                  disease that required treatment with systemic immunosuppressive treatments which
                  may suggest risk for immune-related adverse events (AEs).

                  Note: Patients with autoimmune-related hyperthyroidism, autoimmune-related
                  hypothyroidism who are in remission, or on a stable dose of thyroid-replacement
                  hormone, vitiligo, or psoriasis may be included.

               8. Non-healing wound, skin ulcer (of any grade), or bone fracture.

               9. Patients with prior allogeneic stem cell or solid organ transplantation.

              10. Patients with the following risk factors for bowel perforation (e.g., history of
                  acute diverticulitis or intra-abdominal abscess in the last 3 years; history of
                  gastrointestinal obstruction or abdominal carcinomatosis).

              11. Patients with uncontrolled Type 1 diabetes mellitus. Note: Patients controlled on
                  a stable insulin regimen are eligible.

              12. Patients with uncontrolled adrenal insufficiency.

              13. Any other disease, metabolic dysfunction, physical examination finding, and/or
                  laboratory finding giving reasonable suspicion of a disease or condition that
                  contraindicates the use of an investigational drug or may render the patient at
                  high risk for treatment of complications.

          -  Patients with a known allergy, hypersensitivity, or intolerance to BNT113 or its
             excipients, or to pembrolizumab or its excipients.

          -  Patients who have had a splenectomy.

          -  Patients who have had major surgery (e.g., requiring general anesthesia) within 4
             weeks before screening, or have not fully recovered from surgery, or have a surgery
             planned during the time of trial participation.

          -  Patients who have a known history (testing not required) or has a positive test at
             screening of any of the following:

               1. Human immunodeficiency virus (HIV) 1 or 2.

               2. Hepatitis B (carrier or active infection).

               3. Hepatitis C (unless considered cured 5 years post curative anti-viral therapy).

          -  Patients with another primary malignancy that has not been in complete remission for
             at least 2 years, with the exception of those with a negligible risk of metastasis or
             death (such as adequately treated carcinoma in situ of the cervix, non-invasive basal
             or non-invasive squamous cell skin cancer, localized prostate cancer, non-invasive
             superficial bladder cancer or breast ductal carcinoma in situ).

          -  Patients with any condition for which, in the opinion of the investigator,
             participation would not be in the best interest of the patient (e.g., compromise the
             well-being) or that could prevent, limit, or confound the protocol-specified
             assessments.

        Prior/concomitant therapy:

          -  Patients who have received or currently receive the following therapy/medication:

               1. Chronic systemic immunosuppressive corticosteroid treatment (prednisone >5 mg
                  daily orally [PO] or IV, or equivalent) during the trial. Note: Replacement
                  therapy (e.g., physiologic corticosteroid replacement therapy for adrenal or
                  pituitary insufficiency) is not considered a form of systemic treatment and is
                  permitted.

               2. Prior treatment with other immune modulating agents that was (a) within fewer
                  than 4 weeks (28 days) or 5 half-lives of the agent (whichever is longer) prior
                  to the first dose of BNT113, or (b) associated with immune-mediated AEs that were
                  Grade ≥1 within 90 days prior to the first dose of BNT113, or (c) associated with
                  toxicity that resulted in discontinuation of the immune-modulating agent.

               3. Prior treatment with other immune modulating agents for any non-cancer disease
                  within 4 weeks or 5 half-lives of the agent (whichever is longer) before the
                  first dose of BNT113.

               4. Prior treatment with live attenuated vaccines within 4 weeks before the first
                  dose of BNT113.

               5. Prior treatment with an investigational drug (including investigational vaccines)
                  within 4 weeks or 5 half-lives of the agent (whichever is longer) before the
                  planned first dose of BNT113.

               6. Therapeutic PO or IV antibiotics within 14 days prior to enrollment. • Note:
                  Patients receiving prophylactic antibiotics (e.g., for prevention of a urinary
                  tract infection or chronic obstructive pulmonary disease) may be enrolled.

          -  Prior anti-cancer therapy in the metastatic or in the unresectable recurrent HNSCC
             setting.

          -  Prior treatment with anti-cancer immunomodulating agents, such as blockers of
             programmed death receptor-1 (PD 1), PD-L1, tumor necrosis factor receptor superfamily
             member 9 (TNRSF9, 4 1BB, CD137), OX 40, therapeutic vaccines, cytokine treatments, or
             any investigational agent within 4 weeks before the first dose of BNT113.

          -  Treatment with other anti-cancer therapy including chemotherapy, radiotherapy with
             curative intent, major surgery with curative intent or biological cancer therapy
             within 6 months prior to randomization. Adjuvant hormone therapy used for breast
             cancer in long term remission is allowed.

               -  Note 1: Palliative radiotherapy and palliative surgery are allowed.

               -  Note 2: Prior treatment with bone resorptive therapy, such as bisphosphonates
                  (e.g., pamidronate, zoledronic acid) and denosumab, is allowed assuming that the
                  patients have been on stable doses for ≥4 weeks prior to first dose of trial
                  treatment.

        Other comorbidities:

          -  Current evidence of Common Terminology Criteria for Adverse Events (CTCAE, v5.0) Grade
             >1 toxicity before the start of treatment, except for hair loss and those Grade 2
             toxicities listed as permitted in other eligibility criteria. Patients with Grade 2
             neuropathy may be eligible at investigator's discretion.

          -  Current evidence of new or growing brain or spinal metastases during screening.
             Patients with known brain or spinal metastases may be eligible if they:

               1. had radiotherapy or another appropriate therapy for the brain or spinal
                  metastases,

               2. have no neurological symptoms (excluding Grade ≤2 neuropathy),

               3. have stable brain or spinal disease on the computer tomography (CT) or magnetic
                  resonance imaging (MRI) scan within 4 wks before signing the informed consent,

               4. do not require steroid therapy within 7 d before randomization,

               5. spinal bone metastases are allowed, unless imminent fracture or cord compression
                  is anticipated.

        Other exclusions:

          -  Patients who have previously been enrolled in this trial.

          -  Patients with substance abuse or known medical, psychological, or social conditions
             that may interfere with the patient's participation in the trial or evaluation of the
             trial results.

          -  Patients affiliated with the investigational site (e.g., a close relative of the
             investigator or dependent person, such as an employee or student of the trial site).