Graphene proved to be an excellent material for sensors’ design. Therefore, we decorated it with different heteroatoms (e.g., N, B, S) and use it as electrode material for the design of new stochastic sensors. The graphene paste was modified with oleamides, inulins, dextrins in order to get the stochastic response of the sensor. Biomarkers like MSH6, MLH1, KRAS, p53 were analysed by screening the whole blood, urine, saliva, and tissue samples with the proposed sensors. High sensitivities and low limits of determination were obtained. Excellent correlations between the results obtained using the proposed screening method and the standard method were obtained.