Faits : A. A._, B._ et C._ sont copropriétaires d'étage du bâtiment "E._" sis sur la parcelle n° 248 de la Commune de Lens. Ce bien-fonds jouxte, à l'ouest, la parcelle n° 249, qui supporte l'immeuble "E._". Ces deux biens-fonds sont bordés, au nord, par le chemin public municipal des Devins. B. Dans le courant du mois de septembre 2014, C._ et A._ ont signalé aux autorités communales le déroulement de travaux de construction d'une route menant des Devins à la parcelle n° 1738 sise plus au nord, en direction du chemin de Plans-Mayens, et propriété de F._ et G._. Ils se plaignaient notamment de l'absence de mise à l'enquête de cette réalisation et requéraient une remise en état des lieux. En réponse, le Service technique communal a remis à A._ la copie d'une autorisation du 17 août 2004 (expédiée le 25 novembre 2005) portant sur la réalisation d'une route reliant le chemin des Devins, à la hauteur de la parcelle n° 248, au fonds n° 1738; cette route traverse les parcelles n os 246, 2762, 2809 et 2817. Le 20 octobre 2014, s'adressant au prénommé, le Conseil communal a indiqué avoir procédé à un constat sur les lieux au cours duquel il a été établi que les travaux en cours consistaient à poser du gravier sur l'assiette de la route d'accès au fonds n° 1738, réalisée conformément aux plans acceptés en 2004/2005; des travaux de déplacement de terre ou de modifications de cette route n'ont en revanche pas été constatés. Par acte du 9 février 2015, A._, B._, C._ et les communautés de copropriétaires (ci-après: CPPE) des bâtiments "D._ et E._" ont requis du Conseil communal qu'il ordonne la remise en état. Cette requête a été écartée par décision du 31 mars 2015. Le Conseil communal a notamment retenu que la construction de la route avait débuté en 2006, dans le délai de validité de trois ans du permis de construire, et que les travaux en cours se résumaient à un apport de gravier ne modifiant pas la structure de cet ouvrage. Le 7 mai 2015, A._, B._, C._ et les CPPE des bâtiments "D._ et E._" ont recouru contre cette décision au Conseil d'Etat du canton du Valais. Par décision du 13 janvier 2016, ce dernier a déclaré leur recours irrecevable, jugeant qu'ils n'avaient pas démontré être atteints plus que n'importe qui par les travaux litigieux et leur a, pour ce motif, nié la qualité pour agir. Saisie sur recours du 16 février 2016, la Cour de droit public du Tribunal cantonal du canton du Valais a confirmé l'absence de qualité pour agir des recourants, par arrêt du 22 avril 2016. Elle a considéré que la route d'accès à la parcelle n° 1738 avait été réalisée dans le délai de validité de l'autorisation de construire (trois ans) et conformément à celle-ci. L'instance précédente a par ailleurs estimé que les travaux en cours ne relevaient que de l'entretien, pour lequel aucune autorisation n'était nécessaire. Substituant ses motifs à ceux du Conseil d'Etat, la cour cantonale a considéré que, lorsqu'il est d'emblée certain que l'on se trouve confronté à des travaux autorisés, ou ne nécessitant pas d'autorisation, il ne peut exister d'intérêt digne de protection à obtenir la remise en état, la qualité pour agir ne pouvant être reconnue qu'en présence d'un ouvrage irrégulier. C. Agissant par la voie du recours en matière de droit public, A._, B._, C._ et les CPPE des bâtiments "D._ et E._" demandent principalement au Tribunal fédéral d'annuler l'arrêt attaqué, de leur reconnaître la qualité pour agir et d'ordonner la remise en état des lieux. Subsidiairement, ils concluent au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants. Le Tribunal cantonal et la Commune de Lens ont renoncé à se déterminer. Le Conseil d'Etat conclut au rejet du recours, de même que les intimés, F._ et G._. Les recourants ont répliqué, confirmant leurs conclusions.