NP-hardness of maximum set cover with even/odd coverage requirement
One can rephrase your question as follows:


  Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible.


A very similar problem was shown to be NP-complete by Stadnicki on cstheory:


  Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such that $Ax = b$?


This implies that your problem is intractable as well.