Puedes crear una función de verificación, la cual invocarías antes de insertar.

Propongo esta función que además construirá una consulta con `WHERE` dinámico.

    function dataExists($theTable,$theData)
    { 
        $theWhere = array();
        /*Agregamos cada nombre de columna y marcadores ?*/
        foreach($theData as $k=>$v)
        {
            array_push($theWhere, $k . "=?");
        }
        $sql="SELECT COUNT(*) total FROM $theTable";
        $sql .= " WHERE " . implode(" AND ", $theWhere);
        $theParams=array_values($theData);
        $stmt = Conexion::conectar()->prepare($sql);
        /*En PDO podemos pasar los parámetros en el execute como un array :)*/
        $stmt -> execute($theParams);
        $theTotal=$stmt->fetchColumn();
        $theStatus=($theTotal>0) ? TRUE : FALSE;
        return $theStatus;
    }

##¿Cómo usarla?

Lo primero que **debes respetar de forma estricta es que en el array que la pasas, las claves deben ser exactamente los nombres de columnas que servirán de criterio en el `WHERE`**, pues la función ha sido pensada para que sea **dinámica**, de forma que funcione con cualquier tabla / columnas.

Por lo tanto, deberás pasarle un array parecido a esto:

    $theData = array(
                         'id_usuario'=>1,
                         'id_producto'=>7
                    );

Igualmente, como es lógico, el parámetro `$theTable` debe ser el nombre de la tabla sobre la que quieres consultar, por ejemplo:

    $theTable="nombre_tabla";

La consulta preparada que creará la función en este caso será algo así:

    SELECT COUNT(*) total FROM nombre_tabla WHERE id_usuario=? AND id_producto=?

Nótese que en PDO podemos usar marcadores de `:nombre`, o marcadores de posición `?`. Aquí he optado por esta segunda posibilidad por conveniencia, practicidad y para darle flexibilidad al código, permitiendo un `WHERE` dinámico.

Entonces, `mdlAgregarDeseo` quedaría más o menos así:

    static public function mdlAgregarDeseo($tabla, $datos){
        /*Vamos a recoger con esta variable para hacer un solo return*/
    	$msgInfo="";
    	/*Pasamos la información a nuestra función, la cual devolverá FALSE si no encuentra datos*/
        if (!dataExists($tabla,$datos)){
    	    $stmt = Conexion::conectar()->prepare("INSERT INTO $tabla (id_usuario, id_producto) VALUES (:id_usuario, :id_producto)");
    	    $stmt->bindParam(":id_usuario", $datos["idUsuario"], PDO::PARAM_INT);
    	    $stmt->bindParam(":id_producto", $datos["idProducto"], PDO::PARAM_INT); 
    	    if($stmt -> execute()){
    	        $msgInfo="ok";
    	    }else{
    	        $msgInfo="error";
    	    }	
    	    $stmt-> close();
    	}else{
    		$msgInfo="Datos repetidos, no se puede insertar";
    	}
    	return $msgInfo;
    }

##Configuración a nivel de la base de datos
Puedes implementar `dataExists` aún configurando correctamente tus tablas mediante restricciones de unicidad como ha afirmado @Dibort en su respuesta.

Esto agregará un control adicional de datos duplicados, que nunca viene mal. Y, en el caso de usar el engine `InnoDB` evitará demasiados saltos en tus columnas auto-incrementales, las cuales aumentan aunque una consulta de inserción falle por ser un registro duplicado.

Espero te sea de utilidad.

> ##NB: 
>Sería interesante seguir el criterio de `dataExists` para tus otros métodos. Si al array `$data` le dieras como nombres de clave los
> nombres exactos de las columnas en la base de datos podrías construir
> fácilmente consultas de inserción (o de otro tipo) de una manera
> dinámica. De ese modo tendrías un CRUD que te puede servir para
> cualquier tabla de tu sistema.