Concerning the keilim used for bishul aku”m, it’s a machlokes rishonim. Both opinions are brought in the mechaber. Most poskim seem to follow the stricter opinion (although we’re lenient, as per the mechaber, in the halachos of kashering).
Concerning a mechalel Shabbos, the Chasam Sofer (Y.D. 120) says, regarding stam yaynom, that the reason his wine is assur is neither because of chasnus, nor because of avodah zarah, but rather, it’s a k’nas. The same reasoning would likely apply to bishul, and according to the C.S. it would be a problem despite the fact that we hold bishul aku”m is because of chasnus.