Bonsoir,
la CIA vous a confié [...] une machine à remonter le temps
Il n'est pas précisé à quel moment 
Vu que la CIA n'a pas assez de personnel pour aller sur place, on peut supposer que la machine a été confiée à Martin Riggs et Roger Murtaugh alors qu'ils étaient encore chez eux.
Alors qu'ils sont chez eux, et dès qu'il sont informés de leur mission, ils actionnent la machine et remontent 12 minutes en arrière.
Ils sont alors toujours chez eux, en train de regarder un match de foot universitaire à la télé en mangeant du popcorn.
Ils prennent fissa leur Mustang, roulent à toute allure, et arrivent une demie-heure plus tard au rez-de-chaussée de l'immeuble.
La bombe risque d'exploser dans 18 minutes et quelques secondes.
Martin fouille le rez-de chaussée, puis le 1er, le 2ème et le 3ème étage.
Cela va lui prendre au maximum: 3 + 1 + 3 + 1 + 3 + 1 + 3 = 15 minutes.
Pendant ce temps, Roger est directement monté au 4ème étage et a entrepris de fouiller les étages 4, 5 et 6.
Cela va lui prendre au maximum: 4 + 3 + 1 + 3 + 1 + 3 = 15 minutes.
Même si l'un deux ne trouve l'objet qu'au bout de 15 minutes, il leur restera 3 minutes et quelques secondes pour finir leur sachet de popcorn.
Je ne suis pas sûr que ce soit la réponse attendue, mais la mission me parait ainsi possible.
Edit du 23/10:
BafBaf a écrit:
l'énigme commence au rez de chaussée
En fait, ma réponse n'était même pas complète puisque j'y avais oublié la clause "il faut être deux pour actionner le dispositif"... 
Au lieu de finir son sachet de popcorn, celui qui n'a rien trouvé doit descendre ou monter 3 étages en 3 minutes pour rejoindre son collègue et l'aider à actionner le dispositif dans les dernières secondes.
Autre possibilité:
Les deux protagonistes entrent dans l'immeuble alors qu'il reste 6 minutes et quelques secondes avant l'explosion.
Martin est chargé de fouiller le rez-de chaussée, puis les étages 1, 2 et 3.
Cela va lui prendre au maximum 15 minutes.
Pendant ce temps, Roger est directement monté au 4ème étage et va fouiller les étages 4, 5 et 6.
Cela va lui prendre au maximum 15 minutes.
Dans le pire des cas, ils ne trouvent le dispositif qu'au bout de 15 minutes et la bombe a explosé depuis environ 9 minutes.
Ils remontent le temps de 12 minutes.
A ce moment-là, Martin finit la fouille du rez-de-chaussée et Roger arrive au palier du 3ème étage.
Il leur reste alors 3 minutes et quelques secondes pour rejoindre tous les deux le dispositif et le désactiver avant l'instant fatal.
Si le dispositif est au 6ème étage, Martin a besoin de 6 minutes pour monter au 6ème: c'est fichu...
J'ai sûrement loupé quelque chose... (un troisième homme ? un premier passage manqué devant l'immeuble bien avant les 30 minutes de trajet ? ...)
Cette énigme n'étant classée ni dans énigmes logiques, ni dans énigmes mathématiques, ni dans devinettes, je ne sais plus par quel bout la prendre.
Je jette l'éponge. J'attendrai la lecture de la solution... 