You've got some fundamental misunderstandings about enums here. In C, all an enum does is assign names to literal constants. It's equivalent to using #define, just has slightly nicer syntax.
So when you do:
enum musicalNotes
{
C5 = 425,
Cs5 = 401,
D5 = 379,
Ds5 = 357,
//and more...
};
That's equivalent to
#define C5 425
#define Cs5 401
//etc
Neither one actually allocates anything, they just tell the compiler that when you type "C5" you mean "405". But if you do:
enum
{
C5 = 425,
Cs5 = 401,
D5 = 379,
Ds5 = 357,
//and more...
} musicalNotes;
You've now both told the compiler about your names for all of these values, and directed the compiler to allocate a place to store one of those values called "musicalNotes". However, there's only one place to store one of those values.
What you should be doing depends on what you're trying to achieve. If you just want to be able to write "C5" in your code and have that turn into "425" when it gets compiled, then you just need to define the enum and don't need to allocate any place to store it. All of the note names will just get translated into the integer values at compilation and it all ends up in program memory implicitly because those values are hardcoded into your code.
If you need to be able to store notes to variables, or store a sequence of notes in progmem, then you need to both define the enum values and allocate storage for them. You would then do something like:
enum musicalNotes
{
C5 = 425,
Cs5 = 401,
D5 = 379,
Ds5 = 357,
//and more...
};
//and then...
musicalNotes someTune[] = {C5, D5,C5, Bf3};
//or...
uint16_t someTune[] = {C5, D5,C5, Bf3};
You can assign the enum values to an integer type like uint16_t because, again, enum values are just fancy names for integer constants. As long as the integer type has enough range to store the required values, it all works. You can decorate 'someTune' with the PROGMEM attribute, or static, volatile, whatever you need. The nice thing about this method is that you know exactly what size is getting allocated because you told the compiler, but that comes with the downside that if you add an enum value that's outside of the range for the type you used you're going to have problems.
One other note (heh), with short enum names like you have here, you have more opportunity for collision with other names in the application. Might not be an actual problem, but for example if you have a seven segment display you might also want to have an enum for segments or something and then you have two different values called "C1". So you want to be careful with the scope of those enum definitions, or alternatively define them with a prefix like:
enum musicalNotes
{
NOTE_C5 = 425,
NOTE_Cs5 = 401,
NOTE_D5 = 379,
NOTE_Ds5 = 357,
//and more...
};
Even when you don't have a specific collision to avoid this sort of notation is common because it allows you to look at the value and immediately know what it means and also which part of the application it comes from. Other languages have nicer syntax for enum-like things, where you would refer to "C5" as "musicalNotes.C5" or similar which avoids this whole problem entirely. Newer languages have moved past the terseness of conventional C because it makes things like this easier to understand.