Unfortunately, I forgot about my question here, but I were able to get the images painted as I desired. I think all the answers are present in the documentation, but there is just no example for the current version that connects all the dots. I extended my example above, so far that the only things missing are the exact image positions, but everyone should be able to handle this stuff on their own, as the required function is given as well, I just left out the parameters. And as far as I understand, this method is quite efficient, as the textures are only loaded once and are just reused every frame.

use eframe::egui;
use egui::{Sense, Shape, Vec2};
use epaint::{CircleShape, Color32, Pos2, Stroke};
// new crate, it is important for the function below
use image;

// loads an image from a given path
fn load_image_from_path(path: &std::path::Path) -> Result<egui::ColorImage, image::ImageError> {
    let image = image::ImageReader::open(path)?.decode()?;
    let size = [image.width() as _, image.height() as _];
    let image_buffer = image.to_rgba8();
    let pixels = image_buffer.as_flat_samples();
    Ok(egui::ColorImage::from_rgba_unmultiplied(
        size,
        pixels.as_slice(),
    ))
}

pub struct MyApp {
    // vector full of `CircleShape`s
    circles: Vec<Shape>,
    // another change, the vector should store 'TextureHandle's
    images: Vec<egui::TextureHandle>,
}

impl MyApp {
    fn new(cc: &eframe::CreationContext<'_>,
           coordinates: Vec<(f32, f32)>,
           image_paths: Vec<std::path::Path>) -> Self {
        let circles = coordinates
            .iter()
            .map(|(x, y)| {
                Shape::Circle(CircleShape {
                    center: Pos2 { x: *x, y: *y },
                    radius: 40.0,
                    fill: Color32::from_rgb(255, 0, 0),
                    stroke: Stroke::new(10.0, Color32::from_rgb(130, 0, 0)),
                })
            })
            .collect();
        // next critical step, actually place the images
        let texture_handles: Vec<egui::TextureHandle> = image_paths
            .iter()
            .enumerate()
            .map(|(i, img_path)| {
                cc.egui_ctx.load_texture(
                    format!("image_{}", i),
                    load_image_from_path(img_path).unwrap(),
                    egui::TextureOptions::default())
            })
            .collect();
        Self {
            circles,
            // use loaded texture handles here
            images: texture_handles,
        }
    }
   // some functions to intialize and remove and add shapes
}

impl eframe::App for MyApp {
    fn update(&mut self, ctx: &egui::Context, _frame: &mut eframe::Frame) {
        egui::CentralPanel::default().show(ctx, |ui| {
            ui.heading("Show some circles and images");
            let (_reponse, painter) = ui.allocate_painter(Vec2::new(1000.0, 300.0), Sense::hover());
            painter.extend(self.circles.clone());

            // I want to the painter to place images here
            for texture_handle in self.images.iter() {
                let texture_id = egui::TextureId::from(texture_handle);
                // choose a position where to place the image
                // as you can see this code part is not finished
                let center_position = egui::Rect::from_center_size(...)
                painter.image(
                    texture_id,
                    center_position,
                    egui::Rect::from_min_max(pos2(0.0, 0.0), pos2(1.0, 1.0)),
                    Color32::WHITE,
                );
            }
        });
    }
}