I only used goto in one small section, since I don't have much need for it elsewhere.
[/quote]
You are essentially abusing goto to create a loop. Instead, use an explicit loop:

void Combat::combatChoice(Character& C) {
if (C.health < 0 || C.health == 0) {
cout << "----------------- You died... ------------------" << endl;
cout << "Oh dear, it seems you have died... Game Over." << endl;
return;
}

bool action = false;
while(!action) {
cout << "----------------- Battle Options ------------------" << endl;
C.Display();
cout << "What do you want to do? \n"
<< "Type the number of the action and press enter. \n"
<< "[1] Melee Attack \n"
<< "[2] Gun Attack \n"
<< "[3] Health Potion" << endl;

short choice;
cin >> choice;
switch (choice) {
case 1:
cout << "\n----------------- Battle Results ------------------" << endl;
C.meleeAttack(M);
action = true;
break;

case 2:
cout << "\n----------------- Battle Results ------------------" << endl;
if(C.ammo == 0) {
cout << "You're out of ammo! \n" << endl;
} else {
C.gunAttack(M);
action = true;
}
break;

case 3:
cout << "\n----------------- Battle Results ------------------" << endl;
if(C.potions == 0) {
cout << "You're out of potions! \n" << endl;
} else {
C.useHP();
action = true;
}
break;
}
}
}

Note that this automatically handles the case where the user types an invalid option by looping around, though it is generally nicer to print a specific message in this case.

Another potential improvement is to dynamically remove invalid options from the menu. Something like this:

#include <string>
#include <vector>
struct CombatAction {
typedef void (*ActionFunctionPtr)(Character &character, Monster &monster);
string name;
ActionFunctionPtr action;

CombatAction(const string &name, ActionFunctionPtr action)
:
name(name),
action(action)
{
}
};
void punch(Character &character, Monster &monster) {
character.meleeAttack(monster);
}
void shoot(Character &character, Monster &monster) {
character.gunAttack(monster);
}
void heal(Character &character, Monster & /* unusued */) {
character.useHP();
}
void Combat::combatChoice(Character& C) {
if (C.health < 0 || C.health == 0) {
cout << "----------------- You died... ------------------" << endl;
cout << "Oh dear, it seems you have died... Game Over." << endl;
return;
}

vector<CombatAction> actions;
actions.push_back(CombatAction("Melee Attack", &punch));
if(c.ammo > 0) {
actions.push_back(CombatAction("Gun Attack", &shoot));
}
if(c.potions > 0) {
actions.push_back(CombatAction("Health Potion", &heal);
}

bool action = false;
while(!action) {
cout << "----------------- Battle Options ------------------" << endl;
C.Display();
cout << "What do you want to do? \n";
cout << "Type the number of the action and press enter. \n";
for(size_t i = 0 ; i < actions.size() ; ++i) {
cout << "[" << (i + 1) << "] " << actions.name << '\n';
}

size_t choice;
cin >> choice;
if(choice > 0 && choice <= actions.size()) {
cout << "\n----------------- Battle Results ------------------" << endl;
actions[choice - 1].action(C, M);
action = true;
} else {
cout << "Invalid option!" << endl;
}
}
}

I'm not sure if you are familiar with std::vector or function pointers. Feel free to ask a question if you don't understand what this code is doing.

Note: I haven't compiled or tested any of the code in this post, so caveat emptor.

If you are posting in beginners forum then you shouldn't use goto in your code
Once you reach advanced level... well, then you know yourself.