Starcraft est sensé marcher sous linux, il y a de nombreux tutoriels sous linux. En particulier :
http://appdb.winehq.org/objectManager.php?sClass=version&iId=149
http://doc.ubuntu-fr.org/starcraft
Je pense qu'il n'y a aucun problème pour aller sur bnet, ça marche très bien world of warcraft et warcraft3, mais le lien qui précède semble dire le contraire. N'ayant jamais testé je ne peux pas te dire.
Au niveau des protections sur CD-ROM normalement il n'y a pas de problème si le lecteur CD est configuré dans ton fichier de configuration wine. A noter que pour la version actuelle de warcraft3, sensée tourner sans CD, il faut malheureusement installer le framework visual c++ (y compris sous windows) mais je ne pense pas que starcraft soit concerné. Tu peux aussi avoir des problèmes si tu n'utilises pas la dernière version de wine.
Au niveau des patchs et de brood war, il faut bien veiller à installer le jeu avec wine, ou alors il faudra configurer les clés correspondantes dans la base de registre wine (en particulier les patchs examinent une clé pour trouver le répertoire d'installation).
Tu peux pour les jeux blizzard utiliser indifféremment wine ou cedega. Pour les jeux comme warcraft3 et world of warcraft il faut juste passer l'option "-opengl" si tu passes par wine.
Bonne chance