To investigate the effective linear dielectric constant and third-order nonlinear susceptibility of composite media, in which graded inclusions with radial dielectric anisotropy are randomly embedded in a linear isotropic matrix, we develop an nonlinear anisotropic differential effective dipole approximation (NADEDA). Alternatively, based on a first-principles approach, the exact expressions for and are also derived for the linear dielectric profiles with small slopes. Then, excellent agreement between the two methods is numerically demonstrated. As an application, we further apply the NADEDA to a nonlinear metal-dielectric composite, in which the metal particles possess spatially varying radial dielectric anisotropy, in an attempt to study the nonlinearity enhancement and the figure of merit of the composite. To this end, it is shown that the presence of gradation in the radial dielectric constant plays a crucial role in enhancing the optical nonlinearity as well as the figure of merit.