Nekomata, 19 bytes

2ᵚ~ᵖ{:∫PÄx--v%Ţ≡¿$L

Attempt This Online!

Takes input as l m.

2ᵚ~ᵖ{:∫PÄx--v%Ţ≡¿$L
2ᵚ~                     Find a tuple of [0,1] of length l
   ᵖ{                   Such that:
     :                      Duplicate
      ∫                     Cumulative sum
       P                    Check if all items are positive (so that the tuple starts with 1)
        Ä                   Multiply by 2
         x-                 Subtract [0,1,...,l-1]
           -                Subtract from the original tuple
            v%              Modulus m
              Ţ             Count the occurrences of each item
               ≡            Check if all counts are equal
                ¿$L         And check that there are m distinct items

Nekomata will output all valid solutions in the default mode.

R, 146 126 bytes

\(m,l){lapply(1:2^(l-1)-1,\(i){x=1-i%/%2^(l:1-1)%%2;if(all(sort((cumsum(2*x-1)-x)%%m)==rep(1:m-1,e=l/m)))cat(x,"\n",sep="")})}

Try it on rdrr.io!

Edits:

• Thanks to @pajonk, made into an anonymous function
• Replaced do.call(expand.grid,c(1,rep(list(0:1),l-1))) with iterating or indices 1:2^(l-1)-1, then converting to binary with 1-i%/%2^(l:1-1)%%2
• replaced !any(diff(table(factor(...,0:(m-1)))))
  with all(sort(...)==rep(1:m-1,e=l/m))

05AB1E, 25 24 bytes

oLb¹ùʒSDηO·-ā<+I%ТËiÙgQ

Inspired by @alephalpha's Nekomata's answer, so make sure to upvote that answer as well!

Inputs in the order \$l,m\$.

Try it online or verify both test cases.

Explanation:

o                        # Push 2 to the power the first (implicit) input `l`
 L                       # Pop and push a list in the range [1,2**l]
  b                      # Convert each inner value to a binary-string
   ¹ù                    # Only keep those of length `l`
     ʒ                   # Then filter it further by:
      S                  #  Convert the binary-string to a list of bits
       D                 #  Duplicate it
        ηO               #  Cumulative sum: prefixes and sum each prefix
          ·              #  Double each prefix-sum
           -             #  Subtract that from the list of binary-bits
            ā<+          #  Add the 0-based index to each
               I%        #  Modulo the second input `m`
                 Ð       #  Triplicate that
                  ¢      #  Pop two, and count each value
                   Ëi    #  If all counts are the same:
                     Ù   #   Uniquify the remaining copy
                      g  #   Pop and push its length
                       Q #   Check whether it equals the (implicit) second input `m`
                         # (after which the filtered list is output implicitly)

Jelly, 24 bytes

IŻH_ƲÄ%ĠẈĠḢL⁼
Ø+ṗŒHḢçƇ»0

A dyadic Link that accepts a positive integer, the walk length, on the left and a positive integer, the segment count, on the right and yields a list of lists of 1s and 0s, the walks.

Try it online! Or see the test-suite.

How?

IŻH_ƲÄ%ĠẈĠḢL⁼ - Link 1, Valid +/- Walk?: list of {1,-1}, Potential+/-Walk; #Segments
    Ʋ         - last four links as a monad - f(Potential+/-Walk):
I             -   forward differences
 Ż            -   prefix with a zero
  H           -   halve
   _          -   subtract {Potential+/-Walk}
                (replaces any change of direction with a zero)
                e.g. [1,1,1,-1,-1,1,-1,1,1,1]
                 ->  [1,1,1, 0,-1,0, 0,0,1,1]
                (actually negates everything too, but that doesn't matter!)
     Ä        - cumulative sums
      %       - modulo {#Segments} -> VisitedSegmentIndices
       Ġ      - group indices by their values
        Ẉ     - length of each -> UnlabeledSegmentVisitCounts
         Ġ    - group indices by their values
          Ḣ   - head
           L  - length -> SomeVisitCountGroupSize
            ⁼ - equals {#Segments}
 
Ø+ṗŒHḢçƇ»0 - Link - Make Walks: positive integer, WalkLength; positive integer, #Segments
Ø+         - [1, -1]
  ṗ        - Cartesian power {WalkLength} -> all length WalkLength lists with alphabet [1, -1]
   ŒH      - split into two halves
     Ḣ     - head -> Potential+/-Walks (those lists that start with 1)
       Ƈ   - keep those Potential+/-Walks for which:
      ç    -   call Link 1 as a dyad - Valid +/-Walk?(Potential+/-Walk, #Segments)
        »0 - maximum with zero (replaces each -1 instruction with a zero)

Charcoal, 40 bytes

ＮθＮηΦＥ…Ｘ²⊖ηＸ²η⍘ι²⁼η×θ⌈Ｅθ№Ｅι﹪⁻Σ⁺×…ιξ²νξθλ

Try it online! Link is to verbose version of code. Explanation: Brute force.

Ｎθ                                          Input `m` as a number
  Ｎη                                        Input `l` as a number
      …                                     Range from
        ²                                   Literal integer `2`
       Ｘ                                    Raised to power
          η                                 Input `l`
         ⊖                                  Decremented
            ²                               To literal integer `2`
           Ｘ                                Raised to power
             η                              Input `l`
     Ｅ                                      Map over values
               ι                            Current value
              ⍘                             Converted to base
                ²                           Literal integer `2`
    Φ                                       Filtered where
                       θ                    Input `m`
                      Ｅ                     Map over implicit range
                        №                   Count of
                                       λ    Inner value in
                          ι                 Outer value
                         Ｅ                  Map over digits
                                 ι          Outer value
                                …           Truncated to length
                                  ξ         Innermost index
                               ×            Repeated
                                   ²        Twice
                              ⁺             Concatenated with
                                    ν       Innermost digit
                             Σ              Digital sum
                            ⁻               Subtract
                                     ξ      Innermost index
                           ﹪                Modulo
                                      θ     Input `m`
                     ⌈                      Take the maximum
                   ×                        Multiplied by
                    θ                       Input `m`
                 ⁼                          Equals
                  η                         Input `l`
                                            Implicitly print

JavaScript (V8), 103 bytes

l=>g=(m,z='0',p=0)=>z[l-1]?print(z):[1,0].map(y=>{(f[p%=m]=-~f[p])+!p>l/m||g(m,z+y,p+y);--f[p];p+=m-1})

Try it online!