To make myself clear, I'm aware that one of Superman's major weaknesses is magic, but is that because he's also superpowered by a yellow sun, or just because he's from Krypton? Would Kryptonians be as susceptible to magic under a red sun?
There doesn't appear to have been any suggestion that Kryptonians would be any more resistant to magic under a red sun. I can find only one reference to magic on Krypton, in Superman Vol 1 279. The linked reference doesn't give much detail, but even in the unlikely event that "Ca-Rox, a stage magician from old Krypton who actually had magical powers" used those powers to attack his fellow Kryptonians, it would have been difficult to gauge whether those attacks would have been more or less effective had those Kryptonians had been under a yellow sun.
The Superman comics has not elaborated specifically about how supermans magic weakness works. The best i could find was a Pre-Crisis comic that tried to give an explanation. It claims that the reason is genetic and therefor has nothing to do with sunlight.
In DC Comics Presents Vol 1 18 the magic wielding super-heroine Zatanna tried to learn more about magic and its origin. She found a book that shed some light over the subject and has the following dialog with her father about it.
In short it claims that human beings has a small natural resistance to magic because of our relation to the race Homo Magus, which Zatanna belong to. Superman who comes from Krypton has no such relation and therefor no resistance at all.
If this explanation is still valid efter the Crisis is not known though.
Superman himself has repeatedly said he has "no special defense" against magic, but this is... questionable, at best. "Special defense" meaning yes, he is vulnerable to it, and can be affected by it like other people... but due to some simple aspects of physics, and his physiology, his natural defenses, ---including durability, susceptibility and stamina against such attacks---- would likely still be somewhat above that of normal humans. Think of it this way...
To my knowledge, a "normal" human, has no invulnerability against lightning; there's a very high statistical probability that if one is struck by a certain amount of electricity...they will die, all things being even, correct? Well, Superman has shown on several occasions that he has varied responses to high dose voltages of electricity, from some physical pain [but no injury] at his weakest...
To it slowing him down a little, but him not being negatively impacted for more than a few seconds [go to 6:35 in the video to see him snapping off highly charged electrical wires]...
To him forming a circuit and willingly letting it run through his body for nearly a full minute to power a massive machine when necessary [6:30]
To him basically outspeeding a lightning bolt and shrugging it off with NOT ONE ill effect! [0:12-0:17]
Now keep in mind, the average, "normal" lightning bolt has a massive amount of power; typical lightning bolts contain 1 billion volts of raw electrical charge and between 10,000 to 200,000 amperes of current. We just saw Supes shrug one of those off like "This ain't no thing." The human body has an inherently high resistance to electric current, so without sufficient voltage, a dangerous amount of current cannot flow through the body and cause injury or death. But, as a rough rule of thumb... at base, fifty volts of electricity is sufficient enough to drive a potentially lethal current through a human body.
Now granted, I don't have the exact voltage numbers for each example shown, and we Are dealing with different "versions" of the character....but merely by the visible presence of generated sparks in all of the videos above, we can presume that Supes tanked what could be scientifically estimated as roughly a shit ton more than 50 volts each time.... And he was fine!
Now, let's put Superman against Captain Marvel/Shazam... a magical hero literally empowered by Magic lightning from the Greek Gods.... and watch him take multiple strikes to chest! All that happens is that, yes, he is in pain for a bit...and his costume is ruined [3:22- 3:32...]
Now this is magic lightning! Even if we low-ball it and presume that it has roughly the same voltage as a normal bolt, due to its "magical" nature, it should, by all accounts, either...
[a] completely bypass his powers/super dense molecular structure and thus kill him like any normal human being, at the high end, or
[b] hurt him more than normal lightning, at least, effectively causing some kind of physical injury
Judging from Superman's immediate condition afterwards though [no visible injuries, only costume was burned, no weakness], neither really seems to be the case.
I'm using these animated examples to show that, yes, Superman is somewhat more susceptible to magic... but it does not just "negate" his physical toughness or durability. As a regular Kryptonian, that "vulnerability to magic" still has to bypass some very extraordinary physical and structural defenses, which presumably are far, faaaar beyond the range of regular magic. Remember that magic, like any "power" requires a certain amount of energy, and most magic would generally be tailored to use on earth-bound mortals who aren't unnaturally strong, durable or in possession of an alien [re: non earth standard] energy absorption ability and healing factor.
Think of it this way...
Laws of physics state that in order for a body to be destroyed, a greater force than it can withstand must be applied to it. Another law [simplified] says that a body can withstand about as much force as it can put out. At his weakest, Superman has been shown to be able output billions of tons of force with his muscles alone, just to move or support buildings. And these are low-end feats for him. So logically, he should be able [and has been shown to] survive giga-tons of force; the guy takes that anytime he falls from space and smashes into the earth.
So unless specially tailored....like say, a mental attack, or a "Status affecting" spell, like "sleep for a year!", or a mystical poison of some kind... a "magical attack" would NEED to be able to apply an equivalent amount of force to physically harm him.
I'll make it even simpler....
A magical bullet, fired from an enchanted gun which is made to "always hit the target" it intends too will have an equal effect on both Superman, and a normal human. Neither of them has a "Special defense" against that kind of curse. However...it's still just a measly bullet; while the shots would likely hit both people, Superman, under most logic, would not take any physical harm from said bullet. As a regular piece of earth metal fired at him, it simply won't have the necessary force or density to do him any damage.
You can see this principal at work in Smallville when Clark fights Lana, Chloe and Lois, who are possessed by the spirits of three powerful dead witches. Earlier in the episode, they put a general spell on Clark and all the people at Chloe's birthday party, basically affecting them mentally and releasing their spirit of revelry. Just like all the others, Clark was affected. However, in this scene, Clark has found them out and they are using their magic against him in a battle. Even though Clark's powers are still growing at this stage,he basically "no sells" each shot; everything they throw at him with magic has a physical affect, yes, like pushing him to the ground...but it doesn't hurt him! The only way they can neutralize Clark is to apply the magic to him specifically and directly...
Same principal as the bullet; Clark is vulnerable to magic Spells, but magic attacks have only so much effect because the kid is just too molecularly dense to injure with normal earth items or regular amount of force, even with some potent magic behind it.
On the other hand, if the bullet was non lethal but cursed to make "anyone it hits completely change personalities," [technically a magical spell] well then that is something Superman's physical structure would not be able to defend against. Same with any spell that was made to effect him mentally, or change him in a way that warps reality. Anyone remember in Justice League Unlimited when Wonder Woman was struck directly with Cersei's magic that turned her into a pig? Recall how her bracelets, which are distinctly proof against all magic and force remained untouched?
Same principle; a "transformation" spell may affect Superman, and even a magical bladed weapon which is made to cut flesh... but while a magical creature would be able to perhaps harm him, unless it was Extremely powerful or tailored specifically to bypass his abilities, it wouldn't likely be able to just outright "Destroy him".
His body has proven to be highly resistant to damage and physical harm, even against amounts of force which [on this planet] seem immense.
I am theorizing that this extends to all other Kryptonians.
So yes, someone like Zataana can, say, "put a spell" on Superman or any other Kryptonian the same way she would a human. And depending on how that spell takes affect, they would see some kind of result. Turning them into an animal, for instance, or playing with their mind/soul, or making them clumsy... all of these would hit a Kryptonian much the same way they would hit a human.
Other types of spells, arguably, would be less effective though, simply because a normal Kryptonian's physical durability would need special magic, tailoring, or at least an enormous amount of raw power to overcome. So, hitting them with magic lightning... making monsters to go after them.... trying to freeze or burn them to death.... all of these would require IMMENSE power to overcome a Kryptonian's natural base resistance to electricity, physical trauma, cold and heat [when under a yellow sun, I mean.]
There is a work around around this, however... a skilled magic user could simply use their powers to strip the Kryptonian of their special abilities making them, essentially, Human. That's what Lana and the girls did at the end of the scene, and Clark had to get his powers "jump started" by touching a Kryptonian artifact which trapped a massive amount of power in it. I'm not sure if the law of magic can work like that, because it would be a game breaker on any magical quest, and more evil spell casters would be doing it all the time in fiction. But even in the Smallville example, once a greater power [the Kryptonian crystal] was used, the earth-bound magic failed to have any more effect.
But it IS a possibility; magic users have used specific spells to "Seize" Superman's powers or "bring him down to normal" before.