Obligatory XKCD.

As far as I know there is no case where a goto in C++ is the best tool for the job. I have never had cause to use it in C++ and I would not be overly happy to read or maintain code that uses it either.

Goto has a couple of uses, chiefly amongst them is making loops and exiting out of nested code. Instead it's better to prefer explicit loops and factoring nested code into functions which can be exited using return.

I combination of these alternatives can be applied to your function, including some minor restructuring that makes it a little cleaner:

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

for (;;) {
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;

cout << "\n----------------- Battle Results ------------------" << endl;
switch (choice) {
case 1:
C.meleeAttack(M);
return;

case 2:
if(C.ammo > 0) {
C.gunAttack(M);
return;
}

cout << "You're out of ammo! \n" << endl;
break;

case 3:
if(C.potions > 0) {
C.useHP();
return;
}

cout << "You're out of potions! \n" << endl;
break;

default:
cout << "Whoops you choose an incorrect battle option, try again!\n\n";
}
}
}[/source]

So we've used an infinite loop which is basically saying "keep going till the user provides us with a workable option" (and such a thing would make a good code comment above the loop). Once a valid option has succeeded it exits from the function entirely using mid-function returns.

I find mid-function/early returns are often easier and clearer than using control variables to guide execution out of loops toward the end of a function. There are cases to be made either way.

I think rip-off's second example is better factored, more extensible and offers a superior experience for the user. An observation off the back of it is that having battle actions as member functions on a Character is slightly awkward as it involves a second abstraction for unifying the interface to them: f(C, M)
It may make sense to separate the action concept out as a first-class citizen, e.g. MeleeAttack::apply(Character & C, Monster & M);
Then just register all your Attack actions into the menu vector. You could add other member functions, such as one that predicates whether the action is even valid on the current menu (otherwise the menu code has to know something about what each attack requires).

I actually used goto once or twice in C to decrease number of nested loops in code (it made code look a bit better)... I could've used function there though, but I didn't want (separating that code would be a hell for anyone who would read it).

Basically if you are beginner (and assuming that, because this is in forums For Begginers), you shouldn't use it at all.

goto is not evil in and of itself. There are some very rare occasions when a carefully placed goto can save you a lot of time.

The problem is that goto is essentially an intrinsic for the 'jmp' instruction. If you're good with assembly and understand stack frames and the general behavior of the compiler then you can get away with it, but otherwise just do whatever you have to do to avoid it. The risk of unexpectedly dragging invalid state into somewhere that it doesn't belong (and not having the correct state established for that location) is simply too great.

Even if you do have a perfect grasp of the mechanics and implement a correct use of goto then you'll probably only do it either as a temporary measure or else as some form of bizarre optimization accompanied by 3 pages of commenting.