> Is it possible that the algorithm will fail to find a suitable tile and needs to restart?

Yes, the algorithm can fail. Since it considers only local areas when making decisions, it can easily make a placement that dooms progress later on. The best way to guarantee success in a given amount of compute time is to make tile sets easier to solve, for example by making it possible to transition from any tile to any other in a few hops. But this limits the amount of structure in the output.

> I don't understand, why or how you get those rectangular ponds and lava areas in the first youtube video. I expected them to be far more organic or am I missing something?

It's possible to restrict the tile set so that only rectangular regions are allowed. You do this by creating only convex corners. Here's an example:

Imagine you only have 10 tiles. They are made up of Ground (#) and water (~), and you want rectangular areas of water.

your six tiles are

  ###   ~~~
  ###   ~~~
  ###   ~~~

  #~~  ~~#
  #~~  ~~#
  #~~  ~~#

  ~~~  ###
  ~~~  ~~~
  ###  ~~~

  ### ###
  #~~ ~~#
  #~~ ~~#

  #~~ ~~#
  #~~ ~~#
  ### ###

A valid tiling might be

  #########
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #########

The above uses all tiles except the all ground tile.

I can extend that water rectangle in either direction, but I can't add a feature like

  #~~~~#####
  #~~~~#####
  #~~~~#####
  #~~~~#####
  #~~~~~~~~~
  #~~~~~~~~~

Because that bottom center tile that allows the bend in the water does not exist in your tile set. Adding more tiles like

> How would do you ensure connectivity of areas or points of interest? Any ideas? Would you path a way before or after running the algorithm?

Great question! Let's say you have points of interest A and B, sitting on the ground

  ### ###
  #A# #B#
  ### ###

You'll get a world with As and Bs scattered randomly. So let's connect them with a road (+)

  #+# ###
  #A# #B#
  ### #+#

Now you get worlds like

  ##########+#
  #B##B##B##A#
  #+##+##+####
  #+##+##+#### 
  #A##A##A##B# 
  ##########+# 

Repeating forever. But now add more road pieces

  #+# ###
  #A# #B#
  ### #+#

  #+# ###
  #+# +++
  #+# ###

  ### #+#
  #++ ++#
  #+# ###

Now you have roads that slope up and to the right, always starting at A and ending at B.

  ######
  ####B#
  ####+#
  ####+#
  #++++#
  #+####
  #+####
  #+####
  #+####
  #+####
  #A####
  ######

There are no dead ends because no road dead end tiles exist. Eliminating loops in the road while allowing any direction of travel is more complicated but possible.

This looks like a preview of Advent of Code 2022