Elemental,... pero sólo si sabes usar el PTF

Por el PTF, $2^q-2$ es múltiplo de $q.$ En consecuencia, 6 es múltiplo de $q$ (pues si $4+2^q$ es múltiplo de $2q$, entonces $4+2+2^q-2$ es múltiplo de $q$). De aquí que $q=2$ o $q=3$, y se verifica que 4+4 es múltiplo de 4 y 4+8 es múltiplo de 6. La respuesta es entonces:  todos los primos $q$ tales que $4+2^q$ es múltiplo de $2q$, son 2 y 3.