Passing a single class instance to another class

when you do this:

class Box {
  private:
    Debug _debug;

You are saying that the Box instances will own their Debug instance (as an instance variable), so it's already instantiated for you. So you don't need to instantiate it again.

This should (untested) compile. You can get rid of some constructors
main.ino:

#include "Puzzle.h"
Puzzle puzzle;

void setup() {puzzle.setup();}
void loop() { puzzle.loop();}

Box.cpp

#include "Box.h"
#include <Arduino.h>

void Box::begin() {
  _debug.begin();
  pinMode(28, INPUT_PULLUP);
}

Box.h

#ifndef BOX_H
#define BOX_H
#include "Debug.h"
class Box {
  private:
    Debug _debug;
    
  public:
    void begin();
};
#endif

Debug.cpp

#include "Debug.h"
#include <Arduino.h>

Debug::Debug() : _state(false) {}

void Debug::begin() {
  if (_state == false)
  {
    Serial.begin(9600);
    _state = true;
  }
}

void Debug::newline() {
  if (_state)Serial.println();
}

void Debug::line(const char *messageChar) {
  if (_state)
  {
    const char *p;
    p = messageChar;
    while (*p)
    {
      Serial.print(*p);
      p++;
    }
    newline();
  }
}

void Debug::line(int messageInt) {
  if (_state) {
    Serial.print(messageInt);
    newline();
  }
}

Debug.h

#ifndef DEBUG_H
#define DEBUG_H
class Debug {
  private:
    bool _state;
  public:
    Debug();
    void begin();
    void line(const char *str);
    void line(int);
    void newline();
};
#endif

Puzzle.cpp

#include "Puzzle.h"
#include "Box.h"

void Puzzle::setup() {
  _box.begin();
  _debug.begin();
  _debug.line("Puzzle Setup");
}

void Puzzle::loop() {}

Puzzle.h

#ifndef PUZZLE_H
#define PUZZLE_H

#include "Debug.h"
#include "Box.h"

class Puzzle
{
  private:
    Debug _debug;
    Box _box;

  public:
    void setup();
    void loop();
};

#endif